记录编号	311258	评测结果	AAAAAAAAA
题目名称	道路重建	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	0.021 s
提交时间	2016-09-24 10:24:00	内存使用	7.11 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
int N,M,G[1005][1005]={0},D[1005][1005]={0};
#define INF 99999
void ShortestPath_Floyd(){
	for(int k=1;k<=N;k++){
		for(int v=1;v<=N;v++){
			for(int w=1;w<=N;w++){
				if(D[v][w]>D[v][k]+D[k][w]){
					D[v][w]=D[v][k]+D[k][w];
				}
			}
		}
	}
}
int main(){
	freopen("rebuild.in","r",stdin);
	freopen("rebuild.out","w",stdout);
	int I,J,K,d;
	scanf("%d%d",&N,&M);
	for(int i=1;i<=N;i++){
		for(int j=1;j<=N;j++){
			G[i][j]=INF;
			D[i][j]=INF;
		}
	}
	for(int i=1;i<=M;i++){
		scanf("%d%d%d",&I,&J,&K);
		G[I][J]=min(G[I][J],K);
		G[J][I]=min(G[J][I],K);
		D[I][J]=0;
		D[J][I]=0;
		
	}
	scanf("%d",&d);
	for(int i=1;i<=d;i++){
		scanf("%d%d",&I,&J);
		D[I][J]=G[I][J];
		D[J][I]=G[J][I];
	}
	int A,B;
	scanf("%d%d",&A,&B);
	ShortestPath_Floyd();
	printf("%d",D[A][B]);
	return 0;
}