一只母牛从N块田中的任一块(1≤N≤1000)去参加盛大的母牛聚会，这个聚会被安排在X号田(1≤X ≤N)。一共有M(1 ≤ M ≤ 100,000)条单行道分别连接着两块田，且通过路i需要花Ti(1≤Ti≤100)的时间。每头母牛必需参加宴会并且在宴会结束时回到自己的领地，但是每头牛都很懒而喜欢选择化是最少的一个方案。来时的路和去时的可能不一样。
求每头牛要来回的最短时间。
输入
第一行：三个用空格分开的整数:N,M和X第2到第M+1行:第i+1描述路i，通过三个用空格分开的整数: Ai, Bi和Ti. 是对于从Ai号田到 Bi号田的描述,需要Ti的时间.
输出
第一行:一个整数:对于每头牛所必须花费的时间.（在这段时间内，每头牛可以来回），就是求所有牛再保证自己走的路径是最短的时候求他们中的最大值。
先求一次从X节点出发到其他节点最短路，再将所有边反向，再求一次从X节点出发到其他节点最短路。
以下是我用Dijkstra和Bellman Ford两种算法的解题代码，仅供参考。另外Floyd算法的时间复杂度太高，会TLE的。
//Dijkstra //Memory: 4340K //Time: 94MS #include#include #include #define maxn 1005 using namespace std; bool vis[maxn]; int dis1[maxn]; int dis2[maxn]; int map[maxn][maxn]; int n, m, x; void dijkstra(int* dis) { memset(vis, 0, sizeof(vis)); memset(dis, 0x3f, sizeof(dis1)); dis[x] = 0; for (int i = 1; i <= n; i++) { int index = 0; int minval = 0x3f3f3f3f; for (int j = 1; j <= n; j++) { if(vis[j]) continue; if (minval > dis[j]) { minval = dis[j]; index = j; } } vis[index] = true; for (int j = 1; j <= n; j++) { if (!vis[j]) dis[j] = min(dis[j], dis[index] + map[index][j]); } } } int main() { while (scanf("%d %d %d", &n, &m, &x) != EOF) { int s, e, v; memset(map, 0x3f, sizeof(map)); for (int i = 1; i <= m; i++) { scanf("%d %d %d", &s, &e, &v); map[e][s] = v; } dijkstra(dis1); for (int i = 1; i <= n; i++) { for (int j = i+1; j <= n; j++) swap(map[i][j], map[j][i]); } dijkstra(dis2); int ans = 0; for (int i = 1; i <= n; i++) ans = max(ans, dis1[i]+dis2[i]); printf("%d\n", ans); } return 0; }
//Bellman Ford //Memory: 464K //Time: 16MS #include#include #include #define maxn 1005 using namespace std; struct Edge { int s, e; int v; }e[100006]; int dis1[maxn]; int dis2[maxn]; int n, m, x; void Bellman(int* dis) { memset(dis, 0x3f, sizeof(dis1)); dis[x] = 0; for (int i = 1; i < n; i++) { int hasrelax = false; //如果没有松弛过程了 就代表求到了最短路直接跳出 for (int j = 1; j <= m; j++) { int u = e[j].s; int v = e[j].e; int t = e[j].v; if (dis[v] > dis[u]+t) { dis[v] = dis[u]+t; hasrelax = true; } } if (hasrelax == false) break; } } int main() { while (scanf("%d %d %d", &n, &m, &x) != EOF) { int u, v, t; for (int i = 1; i <= m; i++) { scanf("%d %d %d", &u, &v, &t); e[i].s = u; e[i].e = v; e[i].v = t; } Bellman(dis1); for (int i = 1; i <= m; i++) swap(e[i].s, e[i].e); //将边的方向反向 Bellman(dis2); //求回去的最短路 int ans = 0; for (int i = 1; i <= n; i++) ans = max(ans, dis1[i]+dis2[i]); printf("%d\n", ans); } return 0; }