题目链接：2019 ECNU Campus Invitational Contest-I.Induced Metric Space

题意：

给一个距离矩阵，i行j列表示i点到j点的距离，判断求出该距离矩阵中的未知值，并判断该矩阵是否合法。

该矩阵满足：

1. 每个点到自身的距离为0。
2. 距离全部为非负数。
3. dis(i,j)=dis(j,i)。
4. dis(i,j)<=dis(i,k)+dis(k,j)。

矩阵中的未知值全部用-1表示。

题解：

先把矩阵中所有的-1设为inf(注意inf的大小，题面要求答案不超过1e9)，然后对角补全，并判断该矩阵是否合法。第四点要求用Floyd判断即可，若存在点对(i,j,k)被松弛了，那么就不合法。

参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3fff;
const ll mod = 1e9 + 7;
ll mp[503][503], f[503][503];
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
            {
                scanf("%lld", &mp[i][j]);
                if (mp[i][j] == -1)
                    f[i][j] = inf;
                else
                    f[i][j] = mp[i][j];
            }
        bool flag = 0;
        for (int i = 1; i <= n; i++)
        {
            if (f[i][i] == inf || f[i][i] == 0)
                f[i][i] = 0;
            else
                flag = 1;
        }
        for (int i = 1; i <= n; i++)
            for (int j = i + 1; j <= n; j++)
            {
                if (f[i][j] == inf && f[j][i] == inf)
                    continue;
                else
                {
                    if (f[i][j] == inf || f[j][i] == inf)
                        f[i][j] = f[j][i] = min(f[i][j], f[j][i]);
                    else if (f[i][j] != f[j][i])
                        flag = 1;
                }
            }
        for (int k = 1; k <= n; k++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
            {
                if (mp[i][j] == -1 || i == j)
                    continue;
                if (mp[i][j] != f[i][j] || f[i][j] != f[j][i])
                    flag = 1;
            }
        if (flag)
            puts("NO");
        else
        {
            puts("YES");
            for (int i = 1; i <= n; i++)
            {
                for (int j = 1; j <= n; j++)
                    printf("%lld ", f[i][j]);
                puts("");
            }
        }
    }
    return 0;
}