首页 › 题库 › C/C++编程考级 › C/C++编程八级 › 简答题
简答题 偏难
#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 &lt;limits.h&gt; #include &lt;stdbool.h&gt; #include &lt;stdio.h&gt; #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 &lt;= n; i++) {     dist[i] = INT_MAX;   }   dist[s] = 0;   // 进行n-1轮松弛操作   for (i = 1; i &lt;= n - 1; i++) {     for (j = 0; j &lt; m; j++) {       int u = edges[j].u;       int v = edges[j].v;       int w = edges[j].w;       if (dist[u] != INT_MAX &amp;&amp; dist[u] + w &lt; dist[v]) {         dist[v] = dist[u] + w;       }     }   }   // 检查是否存在负圈   bool hasNegativeCycle = false;   for (j = 0; j &lt; m; j++) {     int u = edges[j].u;     int v = edges[j].v;     int w = edges[j].w;     if (dist[u] != INT_MAX &amp;&amp; dist[u] + w &lt; dist[v]) {       hasNegativeCycle = true;       break;     }   }   // 输出结果   if (hasNegativeCycle) {     printf("Error\n");   } else {     for (i = 1; i &lt;= n; i++) {       if (dist[i] != INT_MAX) {         printf("%d ", dist[i]);       } else {         printf("null ");       }     }     printf("\n");   } } int main() {   int T;   scanf("%d", &amp;T);   while (T--) {     int n, m, s;     scanf("%d %d %d", &amp;n, &amp;m, &amp;s);     int i;     for (i = 0; i &lt; m; i++) {       scanf("%d %d %d", &amp;edges[i].u, &amp;edges[i].v, &amp;edges[i].w);     }     BellmanFord(n, m, s);   }   return 0; }</pre>
这道题暂未补解析。