专栏文章

题解：SP178 ROADNET - Road net

zzby0501_
SP178题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq919wc
此快照首次捕获于
2025/12/04 00:56
3 个月前
此快照最后确认于
2025/12/04 00:56
3 个月前
查看原文

思路：

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

代码：

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...