题解 P2176 【[USACO14FEB]路障Roadblock】

2017-06-29 13:38:03


看起来好多人都要结构体诶。。(蒟蒻不会用stl

就是先跑一遍最短路显然可以证明你需要翻倍的边一定会在最短路上

然后暴力枚举就可以拉

懒得写前向星用了邻接矩阵

有可能有重边然后用了两个邻接矩阵。。(滑稽

时间复杂度最坏情况下n^3

#include<bits/stdc++.h>
using namespace std;
long long n,m,a[2000][2000],b[2000][2000],f[2000],ff[2000],fa[2000],ans,x,y,z;
bool flag[2000];
long long dij(long long x,long long y)//暴力求当x到y的边翻倍之后的最短路
    {
        long long kk=a[x][y];a[x][y]=min(kk*2,b[x][y]);a[y][x]=min(kk*2,b[y][x]);
        memset(f,10,sizeof(f));
        memset(flag,0,sizeof(flag));
        f[1]=0;
        for (long long i=1;i<=n;i++)
            {
                long long k=0;
                for (long long j=1;j<=n;j++)
                    if (!flag[j]&&f[j]<f[k]) k=j;
                flag[k]=true;
                for (long long j=1;j<=n;j++)
                    f[j]=min(f[j],f[k]+a[k][j]);
            }
        a[x][y]=kk;a[y][x]=kk;
        return f[n];
    }
void dfs(long long x)//枚举最短路
    {
        if (!fa[x])return;
        ans=max(ans,dij(fa[x],x));
        dfs(fa[x]);
    }
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    memset(a,10,sizeof(a));memset(b,10,sizeof(b));
    for (long long i=1;i<=m;i++){
        cin>>x>>y>>z;
        b[x][y]=min(b[x][y],max(a[x][y],z));
        b[y][x]=min(b[y][x],max(a[y][x],z));
        a[x][y]=min(a[x][y],z);a[y][x]=min(a[y][x],z);//b[i][j]代表次长边
    }
    memset(f,10,sizeof(f));
    f[1]=0;
    for (long long i=1;i<=n;i++)
        {
            long long k=0;
            for (long long j=1;j<=n;j++)
                if (!flag[j]&&(f[j]<f[k])) k=j;
            fa[k]=ff[k];flag[k]=true;
            for (long long j=1;j<=n;j++)
                if (f[j]>f[k]+a[k][j])f[j]=f[k]+a[k][j],ff[j]=k;
        }
    long long lsg=f[n];dfs(n);
    cout<<ans-lsg;
}