蓝桥杯之最短路问题

问题描述
给定一个n个顶点，m条边的有向图（其中某些边权可能为负，但保证没有负环）。请你计算从1号点到其他点的最短路（顶点从1到n编号）。

输入格式
第一行两个整数n, m。
接下来的m行，每行有三个整数u, v, l，表示u到v有一条长度为l的边。

输出格式
共n-1行，第i行表示1号点到i+1号点的最短路。

样例输入
3 3
1 2 -1
2 3 -1
3 1 2

样例输出
-1
-2

数据规模与约定
对于10%的数据，n = 2，m = 2。
对于30%的数据，n <= 5，m <= 10。
对于100%的数据，1 <= n <= 20000，1 <= m <= 200000，-10000 <= l <= 10000，保证从任意顶点都能到达其他所有顶点。

算法分析：

本题中的图因为有负边，因此只能使用BF或者floyd算法。

这里选用floyd算法，注意本题中的INF INT_MAX/10是为了防止溢出

代码：

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 #include<limits.h>
 5 #define MAXN 20005
 6 #define INF INT_MAX/10
 7 int d[MAXN][MAXN];
 8 int V,E;
 9 int min(int x,int y){
10     return x<y?x:y;
11 }
12 void floyd(){
13 for(int k=1;k<=V;k++)
14 for(int i=1;i<=V;i++)
15 for(int j=1;j<=V;j++)
16 d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
17 }
18 int main()
19 {
20     int u,v;
21     scanf("%d%d",&V,&E);
22     for(int i=1;i<=V;i++)
23     for(int j=i+1;j<=V;j++){
24     d[i][j]=d[j][i]=INF;
25     }
26 
27     for(int i=1;i<=E;i++){
28     scanf("%d%d",&u,&v);
29     scanf("%d",&d[u][v]);
30     }
31     floyd();
32     for(int i=2;i<=V;i++){
33     if(d[1][i]!=INF)
34        printf("%d\n",d[1][i]);
35     }
36     return 0;
37 }

蓝桥杯之最短路问题

推荐阅读