Description
给定n个点，m条有向边
求每个点到1号点的最短距离
Input
第一行两个数为n,m，n表示顶点个数，m表示边的条数。 (1 ≤ n, m ≤ 100 )
接下来m行，每一行有三个数t1、t2 和t3，表示顶点t1到顶点t2的路程是t3。请注意这些t1->t2是单向的。
Output
输出N个数，分别为每个点到1号点的距离
Sample Input
6 9 1 2 1 1 3 12 2 3 9 2 4 3 3 5 5 4 3 4 4 5 13 4 6 15 5 6 4
Sample Output
0 1 8 4 13 17
1 #include<iostream> 2 //#include<fstream> 3 #define inf 0x3f3f3f3f 4 using namespace std; 5 int main(){ 6 int n,m; 7 // fstream file("haha.txt"); 8 // file>>n>>m; 9 cin>>n>>m; 10 int dis[103],u[103],v[103],w[103]; 11 for(int i=1;i<=m;i++){//录入图的信息 12 // file>>u[i]>>v[i]>>w[i]; 13 cin>>u[i]>>v[i]>>w[i]; 14 } 15 for(int i=1;i<=n;i++){//初始化dis数组 16 dis[i]=inf; 17 } 18 dis[1]=0; 19 for(int k=1;k<=n-1;k++){//一共进行n-1次 20 for(int i=1;i<=m;i++){//对每条边进行松弛 21 if(dis[v[i]]>dis[u[i]]+w[i]) 22 dis[v[i]]=dis[u[i]]+w[i]; 23 } 24 } 25 for(int i=1;i<=n;i++){//输出 26 cout<<dis[i]<<' '; 27 } 28 return 0; 29 }
dis数组存储的是各个点到一号点的距离
u,v,w数组分别存储的是 边的起点，边的终点，和边的权值，