题解：AT_abc416_e [ABC416E] Development

· · 题解

upd on 2025.7.30：修改了latex格式相关

题目大意

图上分为关键点（即原题中的机场）和非关键点，边有权值（不一定联通），关键点之间可以花费 K 的时间相互到达。进行如下操作：

Floyd 算法的本质是枚举中间节点，通过中间结点更新任意两点之间的最短路。观察到本题所有修改操作只和一个点有关。即删去更新的点对其他节点之间有影响，当且仅当最短路经过该点。所以每次操作以修改的点为中间结点，枚举图上两点，再次更新最短路，并同时维护答案（也可以到最后一起计算）。

时间复杂度

Floyd 算法预处理全局最短路复杂度为 O(n^3)。

单词询问，枚举图上两点并更新最短路，为 O(n^2)。

总时间复杂度为 O(n^3+Qn^2)，在3.5s的时限下足以通过。

Talk is cheap, show me the code

赛时代码，码风不好见谅：

#include <bits/stdc++.h>

using ll=long long;

#define mems(x,y) memset(x,y,sizeof(x))
#define pii std::pair<int,int>
#define int long long
#define debug if(online_judge)
bool online_judge=true;

// #define MultisetInput true;
const int N = 505;
namespace INPUT_SPACE {
    const int S=(1<<20)+5;
    char B[S],*H,*T;inline int gc(){if(H==T) T=(H=B)+fread(B,1,S,stdin);return (H==T)?EOF:*H++;}
    inline unsigned int read(){unsigned int x,ch;while((ch=gc())<'0'||ch>'9');x=ch^'0';while((ch=gc())>='0'&&ch<='9') x=x*10+(ch^'0');return x;}
}using INPUT_SPACE::read;
int n,m,value,Q,D,sum;
int w[N][N],dis[N][N];
bool vis[N];
void solve(void) {
    n=read(),m=read();
    for(int i=1;i<=n;i++) //初始化dis数组
        for(int j=1;j<=n;j++) 
            if(i==j) dis[i][i]=0;
            else dis[i][j]=1e18;
    for(int i=1;i<=m;i++) {
        int u=read(),v=read(),tmp=read();
        w[u][v]=std::min(w[u][v],tmp);
        w[v][u]=std::min(w[v][u],tmp);
        dis[u][v]=std::min(dis[u][v],tmp);
        dis[v][u]=std::min(dis[v][u],tmp);
    }

    D=read();value=read();
    for(int i=1;i<=D;i++) { //对关键节点打标记
        int u=read();
        vis[u]=true;
    }
    for(int i=1;i<=n;i++) { //更新关键节点之间的距离
        for(int j=1;j<=n;j++) {
            if(vis[i]&&vis[j]) {
                w[i][j]=std::min(w[i][j],value);
                w[j][i]=std::min(w[j][i],value);
                dis[i][j]=std::min(dis[i][j],value);
                dis[j][i]=std::min(dis[j][i],value);
            }
        }
    }
    for(int k=1;k<=n;k++) //Floyd 算法
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                dis[i][j]=std::min(dis[i][j],dis[i][k]+dis[k][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) 
            if(dis[i][j]!=1e18) sum+=dis[i][j];
    Q=read();
    while(Q--) {
        int opt=read();
        if(opt==1) {
            int u=read(),v=read(),tmp=read();
            for(int i=1;i<=n;i++) { //枚举两点，通过新建边更新最短路
                for(int j=1;j<=n;j++) {
                    if(dis[i][j]!=1e18) sum-=dis[i][j];
                    dis[i][j]=std::min({dis[i][j],dis[i][u]+dis[v][j]+tmp,dis[i][v]+dis[u][j]+tmp});
                    if(dis[i][j]!=1e18) sum+=dis[i][j];
                    //这是我更新答案的方式，先用sum减掉原来的答案，再加上更新后的答案，操作2同理
                }
            }
        }
        if(opt==2) {
            int u=read();
            for(int i=1;i<=n;i++) //枚举两点，通过新建关键点更新最短路
                for(int j=1;j<=n;j++)
                    if(vis[j]) {//双向边，答案要乘2
                        if(dis[i][u]!=1e18) sum-=2*dis[i][u];
                        dis[i][u]=std::min(dis[i][u],dis[i][j]+value);
                        dis[u][i]=dis[i][u];
                        if(dis[i][u]!=1e18) sum+=2*dis[i][u];
                    }
            vis[u]=true;
            for(int i=1;i<=n;i++) //更新答案
                for(int j=1;j<=n;j++) {
                    if(dis[i][j]!=1e18) sum-=dis[i][j];
                    dis[i][j]=std::min(dis[i][j],dis[i][u]+dis[u][j]);
                    if(dis[i][j]!=1e18) sum+=dis[i][j];
                }
        }
        if(opt==3) {
            printf("%lld\n",sum);
        }
    }
}

signed main() {
#ifdef ONLINE_JUDGE
    online_judge=false;
#endif
    int T=1;
#ifdef MultisetInput
    scanf("%lld\n",&T);
#endif
    while(T--) solve();
    return 0;
}

闲话

赛后三分钟过掉本题，绝望.jpg。