题解：SP178 ROADNET - Road net

zby0501_ · 2025-02-15 14:04:52 · 题解

思路：

根据题意，我们可以用 floyd 求出所有点到另一点的最短路。然后用两重循环判断图中的点是否满足题意，是的话将其输出就好了。

注意一下，因为图中的路径是双向的，所以处理一半的点就行了。

代码：

#include<bits/stdc++.h>
//#define int long long
using namespace std;
int f[205][205];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j) cin>>f[i][j];
        }
        for(int i=1;i<=n;++i){
            for(int j=i+1;j<=n;++j){
                for(int k=1;k<=n;++k)
                    f[i][k]=min(f[i][k],f[i][j]+f[j][k]);
            }
        }
        for(int i=1;i<=n;++i){
            for(int j=i+1;j<=n;++j){
                bool ff=1;
                for(int k=1;k<=n;++k){
                    if(k!=i && k!=j && f[i][k]+f[k][j]==f[i][j]){
                        ff=0;
                        break;
                    }
                }
                if(ff) cout<<i<<' '<<j<<'\n';
            }
        }
    }
    return 0;
}