BZOJ-1774: [Usaco2009 Dec]Toll 过路费

Description

给你一个n个点，m条边的无向图，带有点权和边权。定义一个路径的代价为路径上经过的边权的和+经过的点的点权的最大值。给出k次询问，每次询问s到t最小代价路径的代价。n<=250 m<=10000 k<=10000

floyd
改变最短路的限定。mp[i][j]表示i->j只经过点权小于max(c[i],c[j])的最短路。只需要将枚举顺序变成从点权由小到大即可。
对于每个询问，枚举点权最大的点是哪个，统计答案。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,q,mp[260][260],c[260];
struct node
{
    int c,id;
}a[300];
bool cmp(node x,node y){return x.c<y.c;}
int main()
{
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",c+i);
        a[i].c=c[i]; a[i].id=i;
    }
    sort(a+1,a+n+1,cmp);
    memset(mp,0x3f,sizeof mp);
    for(int i=1;i<=n;++i) mp[i][i]=0;
    int x,y,z;
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&z);
        if(z<mp[x][y]) mp[x][y]=mp[y][x]=z;
    }
    int s,t,mid;
    for(int k=1;k<=n;++k)
    {
        mid=a[k].id;
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
            {
                s=a[i].id; t=a[j].id;
                if(c[s]>=c[mid]||c[t]>=c[mid])
                    mp[s][t]=min(mp[s][t],mp[s][mid]+mp[mid][t]);
            }
    }
    while(q--)
    {
        scanf("%d%d",&s,&t);
        int ans=mp[s][t]+max(c[s],c[t]);
        for(int i=1;i<=n;++i)
            if(c[i]>=c[s]&&c[i]>=c[t])
                ans=min(ans,mp[s][i]+mp[i][t]+c[i]);
        printf("%d\n",ans);
    }
    return 0;
}