题解：AT_abc416_e [ABC416E] Development

思路

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

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

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

其实本质上就是 DP，我们创建一个数组

a

，设

a_{i,j}

为从城市

i

出发到城市

j

结束的最少时间。

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

CPP

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

，后文会说的。

CPP

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 见祖宗。

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

代码

CPP

#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;
        }
    }
}

题解：AT_abc416_e [ABC416E] Development

文章操作

思路

代码

相关推荐

评论

题解：AT_abc416_e [ABC416E] Development