Description：

每个点有一个点权，每条边有一个边权，一条路径的长度 $=($ 边权之和 $)+($ 经过的所有点中点权的最大值 $)$ ， $q$ 次询问点对之间的最短路。

$1\leqslant n\leqslant 250,1\leqslant q\leqslant 10^4$

Solution：

看算法复杂度应该是 $O(n^3)$ 的，看点对之间复杂度不难想到 $floyed$ ，这个时候需要一些对 $floyed$ 原理的理解。

$floyed$ 的本质是 $f[k][i][j]$ 表示只经过 $[1,k]$ 这些点从 $i$ 到 $j$ 的最短路（ $i$ 和 $j$ 不算），那么这道题既然要求最大，就可以先把点排序，依次循环，这样保证更新的路径上的点权都 $\leqslant k$ ，那么如果 $i$ 和 $j$ 的点权都小于 $k$ 的，就可以用 $f[i][j]+c[k]$ 更新答案，最后 $O(1)$ 回答询问。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m,q;

#define MAXN 251

int f[MAXN][MAXN];

int ans[MAXN][MAXN];

int c[MAXN];

bool cmp(int a,int b){return c[a] < c[b];}

int s[MAXN],p[MAXN];

int main()

{

    scanf("%d%d%d",&n,&m,&q);

    for(int i = 1;i <= n;++i)scanf("%d",&c[i]);

    for(int i = 1;i <= n;++i)s[i] = i;

    sort(s + 1,s + 1 + n,cmp);

    for(int i = 1;i <= n;++i)p[s[i]] = i;

    int a,b,v;

    memset(f,0x3f,sizeof(f));

    for(int i = 1;i <= n;++i)f[i][i] = 0;

    for(int i = 1;i <= m;++i)

    {

        scanf("%d%d%d",&a,&b,&v);

        f[b][a] = f[a][b] = min(f[a][b],v);

    }

    memset(ans,0x3f,sizeof(ans));

    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][s[k]] + f[s[k]][j]);

                if(c[i] <= c[s[k]] && c[j] <= c[s[k]])ans[i][j] = min(ans[i][j],f[i][j] + c[s[k]]);

            }

        }

    }

    for(int i = 1;i <= q;++i)

    {

        scanf("%d%d",&a,&b);

        printf("%d\n",ans[a][b]);

    }

    return 0;

}