题解：AT_abc416_e [ABC416E] Development

· · 题解

思路

蒟蒻第一篇绿题题解，求管理一定要给过呀。

相信大家都学过最短路吧。没学过也没关系。

我来讲一讲多源最短路的 Floyd 算法。

其实本质上就是 DP，我们创建一个数组 a，设 a_{i,j} 为从城市 i 出发到城市 j 结束的最少时间。

当我们在连完所有的双向道路后，可以进行一下一系列操作。

for(int k=1;k<=501;k++)
for(int i=1;i<=501;i++)
for(int j=1;j<=501;j++)
a[i][j]=min(a[i][j],a[i][k]+a[k][j]);

我们首先枚举这个点 k，点 k 为中转点，然后分别枚举 i 和 j，此时如果 i 到 j 的时间比 i 先到 k 再到 j 的时间长，那么我们就把 i 到 j 的最短时间更新为 i 到 k 的最短时间与 k 到 j 的最短时间和。

注意先枚举中转点 k 哈，我就卡在这里卡了很久。

那么，对于从 x 到 y 新加入一条边怎么处理呢？如果全部重新处理一下（即复制一遍上边代码），那复杂度可以达到 O(Q\times n^3) 的，此题的数据无法接受。

我们发现，只有中转点同时带有 x，y 的点才有可能发生改变。此时，我们枚举 i 和 j，如果 i 先到 x 再到 y 再到 j 的时间比原有时间更少，更新求值。

如果 i 先到 y 再到 x 再到 j 的时间比原有时间更少，也更新求值（特别注意！我在这里也卡了好久）。

然后见代码，至于为什么 z 要 \times 2，后文会说的。

cin>>x>>y>>z;
jl=z*2;
a[x][y]=min(a[x][y],jl);
a[y][x]=min(a[y][x],jl);
for(int i=1;i<=501;i++)
for(int j=1;j<=501;j++)
a[i][j]=min(a[i][j],a[i][x]+a[x][y]+a[y][j]),a[i][j]=min(a[i][j],a[i][y]+a[y][x]+a[x][j]);

下面讲重点了！对于机场怎么处理呢？很难空想想出来，这是基于我大量的刷题才可灵光一现的。

我突然发现我们可以再设立一个点，然后每一个有机场的边都对这一个点连一半的时间，最后所有的机场之间不就是两个一半也就是完整的 t 了吗。

但是，由于浮点数不好处理，所以我们就把所有的边都 \times 2 再连接，最后统计答案时除回来就可以了。

对于统计答案，就好说了。

我们只要枚举一下 i，j，然后对 a_{i,j} 加和，最后 \div 2 即可。

最后，警告一下不开 long long 见祖宗。

若有哪里没听懂，欢迎私信问。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,q,k,t,x,y,z,a[505][505],jl,o;
signed main(){
    cin>>n>>m;
    for(int i=1;i<=501;i++)
    for(int j=1;j<=501;j++){
        if(i==j)a[i][j]=0;
        else a[i][j]=1e18;
    }
    for(int i=1;i<=m;i++){
        cin>>x>>y>>z;
        jl=z*2;
        a[x][y]=min(a[x][y],jl);
        a[y][x]=min(a[y][x],jl);
    }
    cin>>k>>t;
    while(k--)cin>>x,a[x][501]=t,a[501][x]=t;
    for(int k=1;k<=501;k++)
    for(int i=1;i<=501;i++)
    for(int j=1;j<=501;j++)
    a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
    cin>>q;
    while(q--){
        cin>>o;
        if(o==1){
            cin>>x>>y>>z;
            jl=z*2;
            a[x][y]=min(a[x][y],jl);
            a[y][x]=min(a[y][x],jl);
            for(int i=1;i<=501;i++)
            for(int j=1;j<=501;j++)
            a[i][j]=min(a[i][j],a[i][x]+a[x][y]+a[y][j]),a[i][j]=min(a[i][j],a[i][y]+a[y][x]+a[x][j]);
        }
        else if(o==2){
            cin>>x;
            a[x][501]=t;
            a[501][x]=t;
            for(int i=1;i<=501;i++)
            for(int j=1;j<=501;j++)
            a[i][j]=min(a[i][j],a[i][x]+a[x][501]+a[501][j]),a[i][j]=min(a[i][j],a[i][501]+a[501][x]+a[x][j]);
        }
        else if(o==3){
            jl=0;
            for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            if(a[i][j]!=1e18)jl+=a[i][j];
            cout<<jl/2<<endl;
        }
    }
}