本文共 1480 字，大约阅读时间需要 4 分钟。
#include#include #include #include #include using namespace std;const int maxn = 1005;const int INF = 1e8;int sign[maxn];int connect[maxn];int dis[maxn];struct node{ int from; int to; int len;} edge[maxn * maxn];int n, m, x, pos, max_time;void add_edge(int op, int ed, int len){ edge[pos].from = connect[op]; connect[op] = pos; edge[pos].to = ed; edge[pos].len = len; pos ++;}int SPFA(int op, int ed){ queue process; memset(sign, 0, sizeof(sign)); fill(dis, dis + maxn, INF); dis[op] = 0; process.push(op); sign[op] = 1; while(!process.empty()) { int this_op = process.front(); process.pop(); sign[this_op] = 0; for(int i = connect[this_op]; i != -1; i = edge[i].from) { int this_ed = edge[i].to; int this_len = edge[i].len; if(dis[this_op] + this_len < dis[this_ed]) { dis[this_ed] = dis[this_op] + this_len; if(!sign[this_ed]) { process.push(this_ed); sign[this_ed] = 1; } } } } return dis[ed];}int main(){ while(~scanf("%d %d %d", & n, & m, & x)) { pos = 0; memset(connect, -1, sizeof(connect)); while(m --) { int a, b, t; scanf("%d %d %d", & a, & b, & t); add_edge(a, b, t); } max_time = 0; for(int i = 1; i <= n; i ++) max_time = max(max_time, SPFA(i, x) + SPFA(x, i)); printf("%d\n", max_time); } return 0;}
题意：
一群牛要聚会。标号1—n，他们要从自己的标号出发，前往指定的x牛的标号位置。要求每条牛来回挑的都是最短路。问其中的牛最大来回总时间是多少。
题解：
这道题是有向最短路，去x的路和回x的路可能不同。所以调用两次SPFA分别求去的最短路和回来的最短路，并相加。
转载地址：http://tctpi.baihongyu.com/