记录编号	348392	评测结果	AAAAAAAAA
题目名称	道路重建	最终得分	100
用户昵称	Я люблю тебя	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2016-11-14 09:50:59	内存使用	0.36 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <algorithm>
using namespace std;

const int maxn=100+10;
int n,m,d;
int a[maxn][maxn],f[maxn];
int s,t;

void spfa();

int main()
{
	freopen("rebuild.in","r",stdin);
	freopen("rebuild.out","w",stdout);

	cin>>n>>m;
	for (int i=1; i<=n;i++)
	for (int j=1; j<=n; j++)
		a[i][j]=INT_MAX/2;
		
	for (int k=0; k<m; k++)
	{
		int i,j,x;
		cin>>i>>j>>x;
		a[i][j]=x; a[j][i]=x;
	}
	cin>>d;
	for (int k=0; k<d; k++)
	{
		int i,j;
		cin>>i>>j;
		a[i][j]*=-1; a[j][i]*=-1;
	}
	for (int i=1; i<=n; i++)
	for (int j=1; j<=n; j++)
	{
		if (a[i][j]>0 && a[i][j]!=INT_MAX/2)
			a[i][j]=0;
		else if (a[i][j]<0)
			a[i][j]*=-1;
	}
	cin>>s>>t;
	
	spfa();
	cout<<f[t]<<endl;
	
	return 0;
}
bool used[maxn];
int q[maxn],front,tail;
void spfa()
{
	for (int i=1; i<=n; i++)
		f[i]=INT_MAX;
	f[s]=0;
	
	front=0; tail=1;
	q[tail]=s; used[s]=true;
	
	while (front!=tail)
	{
		front=(front+1)%maxn;
		int u=q[front];
		used[u]=false;
		
		for (int i=1; i<=n; i++)
		{
			if (f[u]+a[u][i]<f[i])
			{
				f[i]=f[u]+a[u][i];
				if (!used[i])
				{
					tail=(tail+1)%maxn;
					q[tail]=i; used[i]=true;
				}
			}
		}
	}
}