洛谷10048
[CCPC 2023 北京市赛] 图
题目描述
给定一个 n n n 个点的无向正权完全图，请对于每一条边 ( a , b ) (a,b) (a,b)，求出是否存在一个点对 ( x , y ) (x,y) (x,y) 使得 x → y x\rightarrow y x→y 的所有最短路都经过 ( a , b ) (a,b) (a,b)。
输入格式
第一行一个正整数 n ( 1 ≤ n ≤ 500 ) n (1 \le n \le 500) n(1≤n≤500) 表示图的点数。
接下来 n n n 行每行 n n n 个数，构成一个大小为 n × n n\times n n×n 的矩阵，第 i i i 行第 j j j 个数 a i , j ( 1 ≤ a i , j ≤ 1 0 6 ) a_{i,j}(1\leq a_{i,j}\leq 10^6) ai,j(1≤ai,j≤106) 表示 ( i , j ) (i,j) (i,j) 之间的边长度，特别地， a i , i = 0 a_{i,i} = 0 ai,i=0.
保证 a i , j = a j , i a_{i,j}=a_{j,i} ai,j=aj,i。
输出格式
输出一个大小为 n n n 的 01 01 01 矩阵，其中第 i i i 行第 j j j 列为 1 1 1 表示边 ( i , j ) (i,j) (i,j) 满足题目中提出的要求， 0 0 0 表示不满足。
特别的，当 i = j i=j i=j 时输出 0 0 0。
样例 #1
样例输入 #1
4
0 3 2 100
3 0 8 100
2 8 0 10
100 100 10 0
样例输出 #1
0110
1000
1001
0010
#include<bits/stdc++.h>
using namespace std;
const int N=505;
int n,a[N][N],dis[N][N];bool b[N][N];
int main() {scanf("%d",&n);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){scanf("%d",&dis[i][j]);a[i][j]=dis[i][j];}for(int k=1;k<=n;k++){for(int x=1;x<=n;x++){for(int y=1;y<=n;y++){if(x!=k&&y!=k){//int xky=a[x][k]+a[y][k];if(xky<a[x][y]){a[x][y]=xky;}else if(a[x][y]==xky){b[x][y]=1;}}}}}
// for(int i=1;i<=n;i++){//!b[i][j]&
// for(int j=1;j<=n;j++){
// printf("%d ",a[i][j]);
// }puts("");
// }
// for(int i=1;i<=n;i++){//!b[i][j]&
// for(int j=1;j<=n;j++){
// printf("%d ",dis[i][j]);
// }puts("");
// }for(int i=1;i<=n;i++){//for(int j=1;j<=n;j++)printf("%d",!b[i][j]&(dis[i][j]==a[i][j])&!(i==j));puts("");}
}
/*
4
0 3 2 100
3 0 8 100
2 8 0 10
100 100 10 0
4
0 3 2 8
3 0 8 100
2 8 0 10
8 100 10 0
*/
