简答题
偏难
#7349
最短路 给定一个n个点, m条边的有向图, 求从点S出发, 到其它所有点的最短路径. 时间限制:2000 内存限制:65536 输入 第一行一个整数T, 表示有…
最短路
给定一个n个点, m条边的有向图, 求从点S出发, 到其它所有点的最短路径.
时间限制:2000
内存限制:65536
输入
第一行一个整数T, 表示有T组数据 对于每组测试数据, 第一行三个整数n, m, S, 表示有n个点, m条边, 起点为S. 接下来m行, 每行三个整数x, y, z, 代表从x到y有长度为z的边 点的编号从1到n T <= 10, n <= 10000, m <= 20000, |z| <= 10000. 所有数据的n之和 <= 30000, 所有数据的m之和 <= 60000.
输出
对于每组数据: 如果从S点出发可以走入负圈 (即到某些点的最短路径可以无限小), 那么输出一行Error. 否则, 输出一行用空格分隔的n个整数, 其中第i个整数表示从S点到i点的最短路长度. 如果从S点无法到达i点, 则第i个输出为”null”.
样例输入
4
5 7 1
1 2 3
2 3 4
3 4 8
1 3 9
4 5 1
1 4 5
1 5 10
4 4 1
1 2 -4
2 3 8
1 3 5
3 4 0
3 3 2
1 2 -3
2 3 -4
3 1 6
4 2 1
1 2 1
3 4 2
样例输出
0 3 7 5 6
0 -4 4 4
Error
0 1 null null
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//C语言参考答案
#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
#define MAXN 10001
#define MAXM 20001
typedef struct {
int u, v, w;
} Edge;
int dist[MAXN];
Edge edges[MAXM];
void BellmanFord(int n, int m, int s) {
int i, j;
// 初始化距离数组
for (i = 1; i <= n; i++) {
dist[i] = INT_MAX;
}
dist[s] = 0;
// 进行n-1轮松弛操作
for (i = 1; i <= n - 1; i++) {
for (j = 0; j < m; j++) {
int u = edges[j].u;
int v = edges[j].v;
int w = edges[j].w;
if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
}
}
}
// 检查是否存在负圈
bool hasNegativeCycle = false;
for (j = 0; j < m; j++) {
int u = edges[j].u;
int v = edges[j].v;
int w = edges[j].w;
if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
hasNegativeCycle = true;
break;
}
}
// 输出结果
if (hasNegativeCycle) {
printf("Error\n");
} else {
for (i = 1; i <= n; i++) {
if (dist[i] != INT_MAX) {
printf("%d ", dist[i]);
} else {
printf("null ");
}
}
printf("\n");
}
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
int n, m, s;
scanf("%d %d %d", &n, &m, &s);
int i;
for (i = 0; i < m; i++) {
scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].w);
}
BellmanFord(n, m, s);
}
return 0;
}</pre>
这道题暂未补解析。