计蒜客题库

计蒜客题库题解系列:德克萨斯长角牛

难题测试地址:https://nanti.jisuanke.com/t/230

题意:

德克萨斯纯朴的民眾们这个夏天正在遭受巨大的热浪!!!他们的德克萨斯长角牛吃起来不错,可是他们并不是很擅长生产富含奶油的乳制品。Farmer John此时以先天下之忧而忧,后天下之乐而乐的精神,身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任,以减轻德克萨斯人忍受酷暑的痛苦。FJ已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。这些路线包括起始点和终点先一共经过T(1 <= T <= 2,500)个城镇,方便地标号为1到T。除了起点和终点外地每个城镇由两条双向道路连向至少两个其它地城镇。每条道路有一个通过费用(包括油费,过路费等等)。考虑这个有7个城镇的地图。城镇5是奶源,城镇4是终点(括号内的数字是道路的通过费用)。

经过路线5-6-3-4总共需要花费3  (5-> 6)  +  4  (6-> 3)  +  3  (3-> 4)  =  10的费用。 给定一个地图,包含C (1 <= C <= 6,200)条直接连接2个城镇的道路。每条双向道路由两个端点Rs和Re (1 <= Rs <= T; 1 <= Re <= T),和花费(1 <= Ci <= 1,000)组成。求从起始城镇Ts (1 <= Ts <= T)到终点城镇Te(1 <= Te <= T)最小的总费用。

 

这是一道很裸的求最短路的的题目,给个 spfa 模板吧。

 


#include 
#include 
#include 
using namespace std;

const int mmax = 2510;
struct node {
    int en, len;
    int next;
} E[100010];
int p[mmax], num;
void init() {
    memset(p, -1, sizeof p);
    num = 0;
}
void add(int st, int en, int len) {
    E[num].en = en;
    E[num].len = len;
    E[num].next = p[st];
    p[st] = num++;
}
int dis[mmax];
bool vis[mmax];

int spfa(int st, int en) {
    memset(dis, 0x3f, sizeof dis);
    memset(vis, 0, sizeof vis);
    queueq;
    q.push(st);
    vis[st] = 1;
    dis[st] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for (int i = p[u]; i + 1; i = E[i].next) {
            int v = E[i].en;
            if(dis[v] > dis[u] + E[i].len) {
                dis[v] = dis[u] + E[i].len;
                if (!vis[v]) {
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    return dis[en];
}
int main() {
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    init();
    for (int i = 0; i < m; ++i) {
        int u, v, c;
        cin >> u >> v >> c;
        add(u, v, c);
        add(v, u, c);
    }
    cout << spfa(s, t) << endl;
    return 0;
}

评论

你的邮箱地址并不会被公开显示 Required fields are marked *

你可以使用 HTML 标签: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>