题解思路

道路的最小费用Floyd很好求，本来想分别求出i到j的道路最小费用和最小牌照标准，但发现道路费用最小时加上这条道路上的最小牌照标准不一定是最优的。

一条路上的牌照标准是这条路上所有牌照标准的最大值，如果在更新道路最小费用时可以保证牌照标准是递增的，问题就解决了。于是可以用排序。

记录节点原来的位置和牌照标准Ci，把Ci从小到大排，就可以保证更新道路最小费用时牌照标准是递增的。

因为Ci是递增的，枚举i到j的中间点k时，i到j的路上牌照标准最大值一定在i，j，k这三个节点上。为什么呢？

首先，i和j不在Ci递增的行列中，所以不能保证牌照标准最大值不在i或j上；接着，由于k在Ci递增的行列中，k前的节点牌照标准值一定比k小，而k后的节点还没有经过，是后面要用来更新k的。

由于排序后节点的顺序打乱了，数组第i个位置的C不再是第i个节点的C值，而Floyd是按节点原来的顺序求最短路的，要找原来第i个节点的C值就比较麻烦。我们可以再开个数组v，记录原来第i个节点的C值，就可以方便的查找了。

这道题很重要：巧妙利用更新的顺序，解决了传统算法无法解决的问题。该技巧对于floyd的扩展应用有很大的借鉴意义。

#include <bits/stdc++.h>
using namespace std;
int n, m, q, a[260][260], L[260][260], v[260];
struct node{int p, v;}c[260];
bool cmp(node n1, node n2){ return n1.v < n2.v;}
int main()
{
    scanf("%d%d%d", &n, &m, &q);
    memset(L, 63, sizeof(L));//L[i][j]表示点i到点j 过路费 （在考虑牌照费最小的情况下） 
    memset(a, 63, sizeof(a));//a[i][j]表示点i到点j 过路费+牌照费 
    for(int i=1;i<=n;i++)scanf("%d", &v[i]), L[i][i]=a[i][i]=c[i].v=v[i], c[i].p=i;
    
    for(int i=1;i<=m;i++)
    {
        int x, y, f;scanf("%d%d%d", &x, &y, &f);
        L[x][y]=L[y][x]=min(L[x][y], f);
    }
    sort(c+1, c+n+1, cmp);
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)if(i!=c[k].p)
            for(int j=1;j<=n;j++)if(j!=c[k].p && j!=i) 
            {
                L[i][j]=min(L[i][j], L[i][c[k].p]+L[c[k].p][j]);
                a[i][j]=min(a[i][j], L[i][j]+max(max(v[i], v[j]), c[k].v));
            }
    while(q--)
    {
        int x, y;scanf("%d%d", &x, &y);
        printf("%d\n", a[x][y]);
    }
    return 0;
}
/*
5 7 2
2
5
3
3
4
1 2 3
1 3 2
2 5 3
5 3 1
5 4 1
2 4 3
3 4 4
1 4
2 3
*/

/*

道路的最小费用Floyd很好求，本来想分别求出i到j的道路最小费用和最小牌照标准，
但发现道路费用最小时加上这条道路上的最小牌照标准不一定是最优的。

一条路上的牌照标准是这条路上所有牌照标准的最大值，如果在更新道路最小费用时
可以保证牌照标准是递增的，问题就解决了。于是可以用排序。

记录节点原来的位置和牌照标准Ci，把Ci从小到大排，就可以保证更新道路最小费用时牌照标准是递增的。

因为Ci是递增的，枚举i到j的中间点k时，i到j的路上牌照标准最大值一定在i，j，k这三个节点上。为什么呢？

首先，i和j不在Ci递增的行列中，所以不能保证牌照标准最大值不在i或j上；接着，由于k在Ci递增的行列中，
k前的节点牌照标准值一定比k小，而k后的节点还没有经过，是后面要用来更新k的。

由于排序后节点的顺序打乱了，数组第i个位置的C不再是第i个节点的C值，而Floyd是按节点原来的顺序求最短路的，
要找原来第i个节点的C值就比较麻烦。我们可以再开个数组v，记录原来第i个节点的C值，就可以方便的查找了。

这道题很重要：巧妙利用更新的顺序，解决了传统算法无法解决的问题。
该技巧对于floyd的扩展应用有很大的借鉴意义。
*/
#include<bits/stdc++.h>
using namespace std;
int n,m,q,a[260][260],L[260][260],v[260];
struct node{int p,v;}c[260];
bool cmp(node n1,node n2){ return n1.v<n2.v;}
int main()
{
    scanf("%d%d%d",&n,&m,&q);
	memset(L,63,sizeof(L));//L[i][j]表示点i到点j 过路费 （在考虑牌照费最小的情况下） 
	memset(a,63,sizeof(a));//a[i][j]表示点i到点j 过路费+牌照费 
    for(int i=1;i<=n;i++)scanf("%d",&v[i]),L[i][i]=a[i][i]=c[i].v=v[i],c[i].p=i;
    
    for(int i=1;i<=m;i++)
    {
        int x,y,f;scanf("%d%d%d",&x,&y,&f);
        L[x][y]=L[y][x]=min(L[x][y],f);
    }
    sort(c+1,c+n+1,cmp);
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)if(i!=c[k].p)
            for(int j=1;j<=n;j++)if(j!=c[k].p&&j!=i) 
            {
                L[i][j]=min(L[i][j],L[i][c[k].p]+L[c[k].p][j]);
                a[i][j]=min(  a[i][j]   ,   L[i][j]+ max( max(v[i],v[j]) , c[k].v )   );
            }
    while(q--)
    {
        int x,y;scanf("%d%d",&x,&y);
        printf("%d\n",a[x][y]);
    }
    return 0;
}
/*
5 7 2
2
5
3
3
4
1 2 3
1 3 2
2 5 3
5 3 1
5 4 1
2 4 3
3 4 4
1 4
2 3
*/

<br />


<br />