Greg and Graph （Floyd）

题意:

Greg 有一个n个点 是一个有边权的有向图 这个图两个点都有不一样的边(也就意味着 a -> b 和 b -> a的权值是不一样的)

每次操作都会删除一个点,让这个点和其他和它有关系的点都删除.对于每次删除操作,输出操作以前的最短路径之和

思路:

这一题的思路其实与很早之前的并查集删点一样,其实这就是反向加边,通过离线的操作求出最终的答案

#include<bits/stdc++.h>
    
using namespace std;
typedef long long ll;
const int N = 5e2 + 5;
int dist[N][N], n, x[N]; 
ll ans[N];
bitset <N> vis; 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n; cin >> n; 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> dist[i][j];
        }
    } 
    for (int i = 1; i <= n; i++) {
        cin >> x[i]; vis[x[i]] = 1;
    }  
    
    for (int tail = n; tail >= 1; tail--) {
        int k = x[tail];
        vis[k] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) continue;
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                if (!vis[i] && !vis[j]) ans[tail] += dist[i][j];
            }
        }
    } 
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << " \n"[i == n];
    } 
    return 0;
}