G8020 [GESP202603 八级] 子图最短路 题解

知识点：Floyd、增量最短路、区间枚举。

解题思路

枚举区间左端l，逐渐加入右端r。先由原图边与旧区间最短路计算新点r到所有旧点距离，再允许经过r更新所有旧点对；累加每个诱导子图的有限距离。

为什么正确

旧最短路只使用[l,r-1]，新最短路要么不经过r，要么被r分成两段已求出的最短连接，因此增量更新与最短路定义等价。

易错点

加新点前不能使用区间外中转点；不可达距离不参与总和，平行边取最小，模10^9。

复杂度

本实现时间O(n⁴)，空间O(n²)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    const long long INF=1LL<<55;
    vector<vector<long long>>edge(n,vector<long long>(n,INF));
    while(m--) {
        int u,v;
        long long w;
        cin>>u>>v>>w;
        --u;
        --v;
        edge[u][v]=edge[v][u]=min(edge[u][v],w);
    }
    long long ans=0;
    for(int l=0;l<n;l++) {
        vector<vector<long long>>d(n,vector<long long>(n,INF));
        for(int r=l;r<n;r++) {
            vector<long long>dr(n,INF);
            dr[r]=0;
            for(int u=l;u<r;u++) {
                dr[u]=edge[r][u];
                for(int v=l;v<r;v++)dr[u]=min(dr[u],edge[r][v]+d[v][u]);
            }
            for(int u=l;u<r;u++) {
                d[u][r]=d[r][u]=dr[u];
                for(int v=l;v<r;v++)d[u][v]=min(d[u][v],dr[u]+dr[v]);
            }
            d[r][r]=0;
            for(int u=l;u<=r;u++)for(int v=u;v<=r;v++)if(d[u][v]<INF)ans=(ans+d[u][v])%1000000000;
        }
    }
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用18个自行生成的测试点。