专栏文章

题解：AT_abc416_e [ABC416E] Development

sson_son
AT_abc416_e题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miopmsfj
此快照首次捕获于
2025/12/02 23:05
3 个月前
此快照最后确认于
2025/12/02 23:05
3 个月前
查看原文

思路

真服了又是赛后一分钟才过，老是这么演我。
很迅速地就能考虑到，这个点很少边很多的的全员最短路应该用 floyd 来做。
其次可以注意到，这些建了机场的城市就相当于两两之间连了一条边。
接下来考虑每次询问。
对于操作 1 其实非常好搞，也很经典。联想到 floyd 的原理：每次在图中释放一个新点，再两两枚举边，用经过新点的路径更新最短路。这时，我们可以把这个点换成新加的边，再两两枚举边刷新一下经过这条新加边的最短路。
时间复杂度 O(QN2)O(QN^{2})。能搞。
对于操作 2 就有些麻烦了。每次建一个机场都相当于和之前的每个机场连一条边，要对这么多边做操作 1 绝对超时了。这怎么办呢？
我们可以把这群飞机场看做一个团，不管从这个团的那进哪出都是时间 TT 的。
可以发现，我们其实不用管两个点从哪上机从哪下机，因为不管在哪上下所耗的时间都是一样的！所以只需要找到距离每个城市最近的机场就可以了。
这件事需要在初始化，操作 1 和操作 2 的时候做。
之后每两点间的最短路就可以由他们到最近飞机场的距离和再加上 TT。
时间复杂度 O(QN2)O(QN^{2})。能搞。
操作 3 直接暴力。
时间复杂度 O(QN2)O(QN^{2})。搞完！！（致敬zj老师）
AC Code:
CPP
#include<bits/stdc++.h>
using namespace std;
long long _,n,m,k,t,d[505],mp[505][505],ap[505],ans;
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i!=j)mp[i][j]=mp[j][i]=0x3f3f3f3f3f3f;
        }
    }
    for(int i=1;i<=m;i++){
        long long x,y,z;
        scanf("%lld%lld%lld",&x,&y,&z);
        mp[x][y]=mp[y][x]=min(z,mp[x][y]);
    }
    scanf("%lld%lld",&k,&t);
    for(int i=1;i<=k;i++){
        scanf("%lld",&d[i]);
    }
    scanf("%lld",&_);
    for(int i=1;i<=k;i++){
        for(int j=1;j<i;j++){
            mp[d[i]][d[j]]=mp[d[j]][d[i]]=min(mp[d[i]][d[j]],t);
        }
    }
    for(int i=1;i<=n;i++){
        long long nmin=0x3f3f3f3f3f3f3f3f;
        for(int j=1;j<=k;j++){
            if(mp[i][d[j]]<=nmin){
                nmin=mp[i][d[j]];
                ap[i]=j;
            }
        }
    }
    while(_--){
        long long op,x,y,z;
        scanf("%lld",&op);
        if(op==1){
            scanf("%lld%lld%lld",&x,&y,&z);
            mp[x][y]=mp[y][x]=min(mp[x][y],z);
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    mp[i][j]=mp[j][i]=min(mp[i][j],min(mp[i][x]+z+mp[y][j],mp[i][y]+z+mp[x][j]));
                }
            }
            for(int i=1;i<=n;i++){
                long long nmin=0x3f3f3f3f3f3f3f3f;
                for(int j=1;j<=k;j++){
                    if(mp[i][d[j]]<=nmin){
                        nmin=mp[i][d[j]];
                        ap[i]=j;
                    }
                }
            }
        }
        if(op==2){
            scanf("%lld",&x);
            d[++k]=x;
            for(int i=1;i<=k;i++){
                mp[d[i]][x]=mp[x][d[i]]=min(mp[d[i]][x],t);
            }
            for(int i=1;i<=n;i++){
                long long nmin=0x3f3f3f3f3f3f3f3f;
                for(int j=1;j<=k;j++){
                    if(mp[i][d[j]]<=nmin){
                        nmin=mp[i][d[j]];
                        ap[i]=d[j];
                    }
                }
            }
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    mp[i][j]=mp[j][i]=min(mp[i][j],mp[i][ap[i]]+mp[ap[j]][j]+t);
                }
            }
        }
        if(op==3){
            long long sum=0;
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    if(mp[i][j]<0x3f3f3f3f3f3f){
                        sum+=mp[i][j];
                    }
                }
            }
            printf("%lld\n",sum);
        }
    }
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...