记录编号	26818	评测结果	AAAAAAAAA
题目名称	道路重建	最终得分	100
用户昵称	donny	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2011-07-27 15:09:41	内存使用	0.38 MiB

#include <iostream>
#include <fstream>
#include <cmath>
#include <cstring>
#include <iomanip>

using namespace std;

int i,j,k,l,s,t;
int a[101][101],b[101][101],n,m;
int f[101];
int queue[10000];
int head,tail;

void spfa()
{
	head=1;
	tail=1;
	queue[1]=s;
	
	for (i=1;i<=n;i++)
		f[i]=99999999;
	
	f[s]=0;
	
	while (head<=tail)
	{
		for (i=1;i<=n;i++)
			if (b[queue[head]][i]!=-1)
			{
				if (f[queue[head]]+b[queue[head]][i]<f[i])
				{
					tail++;
					queue[tail]=i;
					f[i]=f[queue[head]]+b[queue[head]][i];
				}
			}
		head++;
	}
}


int main()
{
	ifstream fin("rebuild.in");
	ofstream fout("rebuild.out");
	
	fin>>n>>m;
	
	for (i=1;i<=m;i++)
	{
		fin>>j>>k>>l;
		a[j][k]=l;
		a[k][j]=l;
	}
	
	fin>>m;
	
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
		{
			if (a[i][j]==0)
			{
				b[i][j]=-1;
			}
			else
			{
				b[i][j]=0;
			}
		}
		
	for (i=1;i<=m;i++)
	{
		fin>>j>>k;
		b[j][k]=a[j][k];
		b[k][j]=a[k][j];
	}
	
	fin>>s>>t;
	
	spfa();
	fout<<f[t];
	
	fin.close();
	fout.close();
	
	return 0;
}