题解：CF416E President's Path

GavinCQTD · 2025-12-18 16:22:11 · 题解

很妙啊。

先考虑朴素做法，跑一遍全源最短路，枚举起点和终点还有每条边，拼起来看边在不在最短路上。复杂度是 O(n^4) 的，显然过不了。

我们是必然要枚举起点和终点的，在内部肯定不能枚举边了。我们把边通过度转换到点上，具体来说，统计有多少条连接着这个点的边是在最短路上的。接着只需要枚举点，看点在不在最短路上，在的话把度累加上去就行了。复杂度是 O(n^3) 的，很优啊。

/******************************
 - @GavinCQTD
 - "E. President's Path"
 - # https://codeforces.com/problemset/problem/416/E
 - 4000 ms
******************************/

#include <iostream>
#include <cassert>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

struct Element{
    int x,y,l;
};

constexpr ull INF=1e17;

int n,m,ans[505][505];
ull f[505][505],g[505][505];
Element el[125005];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m;

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            g[i][j] = INF;
            if(i==j){
                continue;
            }
            f[i][j] = INF;
        }
    }

    for(int i=1;i<=m;i++){
        cin >> el[i].x >> el[i].y >> el[i].l;
        f[el[i].x][el[i].y] = min(f[el[i].x][el[i].y],(ull)el[i].l);
        f[el[i].y][el[i].x] = min(f[el[i].y][el[i].x],(ull)el[i].l);
        g[el[i].x][el[i].y] = f[el[i].x][el[i].y];
        g[el[i].y][el[i].x] = f[el[i].y][el[i].x];
    }

    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 s=1;s<=n;s++){
        static int tmp[505];
        for(int i=1;i<=n;i++){
            tmp[i] = 0;
        }

        for(int t=1;t<=n;t++){
            for(int k=1;k<=n;k++){
                if(f[s][k]+g[k][t]==f[s][t]){
                    tmp[t]++;
                }
            }
        }

        for(int t=1;t<=n;t++){
            for(int i=1;i<=n;i++){
                if(f[s][i]+f[i][t]==f[s][t]){
                    ans[s][t] += tmp[i];
                }
            }
        }
    }

    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
            if(f[i][j]>=INF){
                cout << "0 ";
            }
            else{
                cout << ans[i][j] << " ";
            }
        }
    }
    cout << "\n";

    return 0;
}