C--最短路
Time Limit: 7000MS
Memory Limit: 65536KB
Problem Description
给出一个带权无向图,包含n个点,m条边。求出s,e的最短路。保证最短路存在。
Input
多组输入。
对于每组数据。
第一行输入n,m(1<= n && n<=5*10^5,1 <= m && m <= 2*10^6)。
接下来m行,每行三个整数,u,v,w,表示u,v之间有一条权值为w(w >= 0)的边。
最后输入s,e。
接下来m行,每行三个整数,u,v,w,表示u,v之间有一条权值为w(w >= 0)的边。
最后输入s,e。
Output
对于每组数据输出一个整数代表答案。
Example Input
3 1 1 2 3 1 2
Example Output
3
Hint
Author
zmx
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int n,m,i,k,s,e,check;
int u[5000100],v[5000100],w[5010000]; //只能用bellman,因为数据较大
int dis[5000010]; //二维数组会爆,spaf看不懂,
#define INF 0x3f3f3f3f
int main() //看的模板,不太明白
{while(scanf("%d%d",&n,&m) != EOF){memset(u,0,sizeof(u));memset(v,0,sizeof(v));memset(w,0,sizeof(w));memset(dis,INF,sizeof(dis));for(i=1;i <= m;i++){scanf("%d%d%d",&u[i],&v[i],&w[i]); //记录道路信息}scanf("%d%d",&s,&e);dis[s] = 0;for(k = 0;k <= n-1;k++)//最差需要调整嗯-1次{check = 0; // 标记变量for(i = 0;i <= m;i++){if(dis[v[i]]>dis[u[i]] + w[i]){dis[v[i]] = dis[u[i]] +w[i];check = 1;}if(dis[u[i]] > dis[v[i]] + w[i]){dis[u[i]] = dis[v[i]] +w[i];check = 1;}}if(check == 0) //调整结束,break;}printf("%d\n",dis[e]);}return 0;
}