题目链接:
I - Induced Metric Space
题目大意:首先是T组测试样例,然后给你一个n*n的矩阵,然后a[i][j]代表i到j的距离是a[i][j]。然后-1代表当前的点的距离不知道,让你填空。要求自己到自己距离是0,a[i][j]=a[j][i]。a[i][j]为i到j的最短距离。
具体思路:前面是一堆非法情况的判断。然后floyed求最短路,如果当前的点是固定的值并且还可以松弛,那么就是非法的。注意数据范围
floyed竟然打错了。。
AC代码:
1 #include<bits/stdc++.h> 2 using namespace std; 3 # define ll long long 4 # define LL_inf 1e9 5 const int maxn = 2e5+100; 6 const int N = 500+100; 7 int a[N][N]; 8 int vis[N][N]; 9 int n,flag; 10 void floyed() 11 { 12 for(int i=1; i<=n; i++) 13 { 14 for(int j=1; j<=n; j++) 15 { 16 for(int k=1; k<=n; k++) 17 { 18 if(!vis[j][k]&&a[j][k]>a[j][i]+a[i][k]) 19 { 20 flag=0; 21 } 22 a[j][k]=min(a[j][k],a[j][i]+a[i][k]); 23 } 24 } 25 } 26 } 27 int main() 28 { 29 int T; 30 scanf("%d",&T); 31 while(T--) 32 { 33 flag=1; 34 memset(vis,0,sizeof(vis)); 35 scanf("%d",&n); 36 for(int i=1; i<=n; i++) 37 { 38 for(int j=1; j<=n; j++) 39 { 40 scanf("%d",&a[i][j]); 41 if(a[i][j]==-1) 42 vis[i][j]=1; 43 } 44 } 45 for(int i=1; i<=n; i++) 46 { 47 if(a[i][i]==-1) 48 a[i][i]=0,vis[i][i]=0; 49 if(a[i][i]!=0) 50 { 51 flag=0; 52 break; 53 } 54 } 55 for(int i=1; i<=n; i++) 56 { 57 for(int j=i; j<=n; j++) 58 { 59 if(a[i][j]==-1&&a[j][i]!=-1) 60 { 61 a[i][j]=a[j][i]; 62 vis[i][j]=0; 63 } 64 if(a[i][j]!=-1&&a[j][i]==-1) 65 { 66 a[j][i]=a[i][j]; 67 vis[j][i]=0; 68 } 69 if(a[i][j]!=a[j][i]) 70 { 71 flag=0; 72 break; 73 } 74 } 75 if(!flag) 76 break; 77 } 78 if(!flag) 79 printf("NO\n"); 80 else 81 { 82 for(int i=1; i<=n; i++) 83 { 84 for(int j=1; j<=n; j++) 85 { 86 if(vis[i][j]==0) 87 continue; 88 a[i][j]=LL_inf; 89 } 90 } 91 floyed(); 92 for(int i=1; i<=n; i++) 93 { 94 for(int j=1; j<=n; j++) 95 { 96 if(a[i][j]!=a[j][i]) 97 { 98 flag=0; 99 break; 100 } 101 } 102 if(!flag) 103 break; 104 } 105 if(!flag) 106 printf("NO\n"); 107 else 108 { 109 printf("YES\n"); 110 for(int i=1; i<=n; i++) 111 { 112 for(int j=1; j<=n; j++) 113 { 114 if(j==1) 115 printf("%d",a[i][j]); 116 else 117 printf(" %d",a[i][j]); 118 } 119 printf("\n"); 120 } 121 } 122 } 123 } 124 return 0; 125 }