Description 给出n个点的距离矩阵，判断其是否是一个最短距离矩阵，如果是则找到一个满足条件的距离矩阵使得该矩阵的最短距离矩阵为所给矩阵 Input 第一行一整数n表示点数，之后一个n*n矩阵d表示距离矩阵(1<=n<=300,1<=d[i][j]<=1e9) Output 如果该矩阵不是最短距离矩阵则输出-1，否则输出一个满足条件的距离矩阵使得该矩阵的最短距离矩阵为所给矩阵，输出任一解即可 Sample Input 3 0 1 2 1 0 3 2 3 0 Sample Output 0 1 2 1 0 4 2 5 0 Solution 用Floyd跑一遍最短路求出该矩阵的最短距离矩阵，判断两个是否相等，不相等输出-1，否则把该矩阵直接输出即可，因为这个矩阵本身就是一个合法解 Code
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<queue> #include<map> #include<set> #include<ctime> using namespace std; typedef long long ll; #define INF 0x3f3f3f3f #define maxn 333 int n,m[maxn][maxn],mm[maxn][maxn]; int main() { int n; while(~scanf("%d",&n)) { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&m[i][j]),mm[i][j]=m[i][j]; for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) mm[i][j]=min(mm[i][j],mm[i][k]+mm[k][j]); int gg=0; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) gg+=abs(mm[i][j]-m[i][j]); if(gg)printf("-1\n"); else { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) printf("%d%c",m[i][j],j==n?'\n':' '); } } return 0; }