C–最短路 Description
给出一个带权无向图，包含n个点，m条边。求出s，e的最短路。保证最短路存在。 Input
多组输入。
对于每组数据。
第一行输入n，m(1<= n && n<=510^5,1 <= m && m <= 310^6)。 接下来m行，每行三个整数，u,v,w,表示u，v之间有一条权值为w(w >= 0)的边。 最后输入s，e。 Output
对于每组数据输出一个整数代表答案。 Sample Input
3 1
1 2 3
1 2
Output
3
#include <bits/stdc++.h> using namespace std; int dis[500004], i, k, n, m, check, u[4000004], v[4000004], w[4000004]; void Bellman(); int main() { int s, e, x, y, z, t; while(scanf("%d %d", &n, &m) != EOF) { t = 1; for(i = 1; i <= m; i++) { scanf("%d %d %d", &x, &y, &z); u[t] = x, v[t] = y, w[t] = z; t++; u[t] = y, v[t] = x, w[t] = z; t++; } scanf("%d %d", &s, &e); m = m * 2; for(i = 1; i <= n; i++) dis[i] = INT_MAX; dis[s] = 0; Bellman(); printf("%d\n", dis[e]); } return 0; } void Bellman() //Bellman-Ford 算法 { for(k = 1; k < n; k++) { check = 0; for(i = 1; i <= m; i++) { if(dis[u[i]] != INT_MAX && dis[v[i]] > dis[u[i]] + w[i]) //如果不判断dis是否为最大值，可能会溢出 { dis[v[i]] = dis[u[i]] + w[i]; check = 1; } } if(check == 0) break; } return ; }//二维数组直接爆了
#include<bits/stdc++.h> using namespace std; #define inf 999999 int a[50001][50001]; int visit[50001]; int dis[50001]; int n,m; int k; int minn; int s,e; int main() { while(cin>>n>>m) { memset(a,0,sizeof(a)); memset(visit,0,sizeof(visit)); for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) { if(i==j) a[i][j]=0; else a[i][j]=inf; } for(int i=0; i<m; i++) { int u,v,w; cin>>u>>v>>w; a[u][v]=a[v][u]=w; } cin>>s>>e; for(int i=1; i<=n; i++) { dis[i]=a[s][i]; } // for(int i=1; i<=n; i++) // cout<<dis[i]<<" "; visit[s]=1; for(int i=1; i<=n-1; i++) { minn=inf; for(int j=1; j<=n; j++) { if(visit[j]==0&&dis[j]<minn) { minn=dis[j]; k=j; } } visit[k]=1; for(int j=1; j<=n; j++) { if(a[k][j]<inf) { if(dis[j]>dis[k]+a[k][j]) dis[j]=dis[k]+a[k][j]; } } } // for(int i=1; i<=n; i++) // cout<<dis[i]<<" "; cout<<dis[e]<<endl; } return 0; } /*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*/