【题意】给定无向图，距离定义为边权和+最大点权，询问若干个两点最短距离。n<=250。
【算法】排序+floyd
【题解】考虑floyd的过程是每次找一个中转点，为了在当前找到一条新路径时方便地统计路径上的最大点权：
对点权进行排序，按点权从小到大的顺序枚举中转点，这样最大点权一定是i,j,k三点中的较大值。
注意到，最短路map[][]是独立于最短距离d[][]的，d[][]每条路径中依赖map[][]+max(i,j,k)。
本题关键在于排序中转点权，从而方便统计路径最大点权。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
int n,m,kind,d[maxn][maxn],map[maxn][maxn],a[maxn];
struct cyc{int num,id;}b[maxn];
bool cmp(cyc a,cyc b){return a.num<b.num;}
int main(){
scanf("%d%d%d",&n,&m,&kind);
for(int i=;i<=n;i++)scanf("%d",&a[i]),b[i]=(cyc){a[i],i};
sort(b+,b+n+,cmp);
int u,v,w;
memset(map,0x3f,sizeof(map));memset(d,0x3f,sizeof(d));
for(int i=;i<=n;i++)map[i][i]=;
for(int i=;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
map[u][v]=map[v][u]=min(map[u][v],w);
}
for(int l=;l<=n;l++){
int k=b[l].id;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++){
map[i][j]=min(map[i][j],map[i][k]+map[k][j]);
d[i][j]=min(d[i][j],map[i][j]+max(a[k],max(a[i],a[j])));
}
}
for(int i=;i<=kind;i++){
scanf("%d%d",&u,&v);
printf("%d\n",d[u][v]);
}
return ;
}