题解 | A118194.午枫的路线封闭

原题链接：A118194.午枫的路线封闭

本题使用 Floyd 最短路解决。

Floyd 算法

Floyd 算法是一种以类似动态规划的逻辑，使用数组 dis 存储最短路长度，具体流程为：考虑枚举一个中间点 $k$ ，选择从起点到中间点的最短路长度 + 从中间点到终点的最短路长度之和的最小值作为最短路长度。形式化表达为，设 $dis_{i,j}$ 为从 $i$ 到 $j$ 的最短路长度，从 $i$ 到 $j$ 的最短路转移方程就是 $dis_{i,j} = \min _{k=1}^{n} dis_{i,k} + dis_{k,j}$ 。

标准模板（片段）：

for(int i = 0;i < N;i ++) 
    for(int j = 0;j < N;j ++)
        dis[i][j] = 1e18;
 
for(int i = 1;i <= m;i ++) {
    int u,v,w;
    cin >> u >> v >> w;
    dis[u][v] = w;
    dis[v][u] = w;
}

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

其中 dis 为最短路长度数组，$n$ 为点的数量。

本题思路

事实上，Floyd 可以处理动态加边问题，只需要重新枚举各个起点和终点以该边的起点或终点为中间点更新最短路即可。

但本题的操作 1 为删边。

所以我们不难想到倒着离线处理，把正着的删边当成倒着的加边，倒着处理询问，如果操作删除了一条边那就加上这条边处理之前的询问。

AC 代码：

#include <bits/stdc++.h>
#include <bits/stdc++.h>

#define int long long
//记得开 long long


using namespace std;
const int N = 305;
const int M = 6e5 + 10;

int n,m,q,f[N][N];

//对于边离线处理

struct edge {
    int u;
    int v;
    int w;
} ed[N*N];

//对于操作离线处理

struct opt {
    int op;
    int x;
    int y;
} o[M];

bool vis[M];//到最后没被删除的边
int ans[M];//答案
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    for(int i = 0;i < N;i ++) {
        for(int j = 0;j < N;j ++) {
            f[i][j] = 1e18; //初始设置距离为 inf
        }
    }


    cin >> n >> m >> q;

    //读入边
    for(int i = 1;i <= m;i ++) {
        int u,v,w;
        cin >> u >> v >> w;
        ed[i].u = u;
        ed[i].v = v;
        ed[i].w = w;
    }

    for(int i = 1;i <= q;i ++) {
        int op,x,y;
        cin >> o[i].op;
        //离线操作
        if(o[i].op == 1) {
            cin >> x;
            o[i].x = x;
            vis[x] = 1;
        } else {
            cin >> x >> y;
            o[i].x = x;
            o[i].y = y;
        }
    } 
    //先处理到最后没删的边
    for(int i = 1;i <= m;i ++) {
        if(vis[i]) continue;
        f[ed[i].u][ed[i].v] = min(f[ed[i].u][ed[i].v], ed[i].w);
        f[ed[i].v][ed[i].u] = min(f[ed[i].v][ed[i].u], ed[i].w);
    }
    for(int i = 1;i <= n;i ++) {
        f[i][i] = 0;
    }
    //先跑一遍 Floyd 最短路
    for(int k = 1;k <= n;k ++) {
        for(int i = 1;i <= n;i ++) {
            for(int j = 1;j <= n;j ++) {
                f[i][j] = min(f[i][j],f[i][k] + f[k][j]);
            }
        }
    }


    //倒着处理
    for(int i = q;i >= 1;i --) {
        if(o[i].op == 1) {
            int u = ed[o[i].x].u;
            int v = ed[o[i].x].v;
            int w = ed[o[i].x].w;
            //把正着删边改为倒着加边
            f[u][v] = min(f[u][v], w);
            f[v][u] = min(f[v][u], w);
            for(int x = 1;x <= n;x ++) {
                for(int y = 1;y <= n;y ++) {
                    f[x][y] = min(f[x][y],f[x][u] + f[u][y]);
                }
            }

            for(int x = 1;x <= n;x ++) {
                for(int y = 1;y <= n;y ++) {
                    f[x][y] = min(f[x][y],f[x][v]+f[v][y]);
                }
            }
        } else {
            //记录答案
            if(f[o[i].x][o[i].y] == 1e18) {
                ans[i] = -1;
            } else {
                ans[i] = f[o[i].x][o[i].y];
            }
        }
    }
    //输出
    for(int i = 1;i <= q;i ++) {
        if(ans[i] == 0) continue;
        cout << ans[i] << '\n';
    }
    return 0;
}

感谢观看。

创作不易，希望给我一个点赞。