记录编号	514396	评测结果	AAAAAAAAAA
题目名称	[USACO Dec09] 过路费	最终得分	100
用户昵称	@@@	是否通过	通过
代码语言	C++	运行时间	0.116 s
提交时间	2018-10-16 09:39:44	内存使用	0.81 MiB

#include<iostream>
#include<cstdio>
#include<stack>
#include<algorithm>
using namespace std;
int n,m,q;
int e[255][255],f[255][255];
int r[255];

int point[255];
bool mmp(int x,int y)
{
	return point[x] < point[y];
}
int main()
{
	freopen("toll.in","r",stdin);
	freopen("toll.out","w",stdout);
	scanf("%d%d%d",&n,&m,&q);
	
	for(int i = 1;i <= n;i++)
	{
		r[i] = i;
		for(int j = 1;j <= n;j++)
		{
			f[i][j] = e[i][j] = 1e9;
		}
		e[i][i] = 0;
	}
	for(int i = 1;i <= n;i++)
	{
		scanf("%d",&point[i]);
	}
	int u,v,w;
	sort(r+1,r+1+n,mmp);
	for(int i = 1;i <= m;i++)
	{
		scanf("%d%d%d",&u,&v,&w);
		//e[r[u]][r[v]] = w;
		e[u][v] = min(e[u][v],w);
		//e[r[v]][r[u]] = w;
		e[v][u] = e[u][v];
	}
	
	for(int l = 1;l <= n;l++)
	{
		int k = r[l];
		for(int ii = 1;ii <= n;ii++)
		{
			int i = ii;
			for(int jj = 1;jj <= n;jj++)
			{
				int j = jj;
				e[i][j] = min(e[i][j],e[i][k]+e[k][j]);
				f[i][j] = min(f[i][j],e[i][j]+max(point[k],max(point[i],point[j])));
			}
		}
	}
	for(int i = 1;i <= q;i++)
	{
		scanf("%d%d",&u,&v);
		printf("%d\n",f[u][v]);
	}
	return 0;
	
}