http://www.lydsy.com/JudgeOnline/problem.php?id=1774

题意

一个图，每条边有边权，每个点也有点权，

定义两个点之间的费用为，两点之间的路径长度加上路径上最大的一个点权。

询问任意两个点对的最小费用。

题解

一看到是求任意点对的费用，就要floyd

然后floyd的性质保证当过渡点循环到k时，所有经过的点的编号<=k;

于是，我们按点权从小到大排序后，floyd。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=251;
int f[N][N],ans[N][N],num[N],n,m,p;
struct node
{
	int w,n;
}a[N];
inline bool cmp(node a,node b)
{
	return a.w<b.w;
}
int main()
{
	memset(f,63,sizeof(f));
	memset(ans,63,sizeof(ans));
	scanf("%d%d%d",&n,&m,&p);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i].w);a[i].n=i;
		f[i][i]=0;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++)	num[a[i].n]=i;
	int x,y,z;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		x=num[x];y=num[y];
		f[x][y]=f[y][x]=min(f[x][y],z);
	}
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
			{
				f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
				ans[i][j]=min(ans[i][j],f[i][j]+max(a[k].w,max(a[i].w,a[j].w)));
			}
	for(int i=1;i<=p;i++)
	{
		scanf("%d%d",&x,&y);
		printf("%d\n",ans[num[x]][num[y]]);
	}
}