http://acm.timus.ru/problem.aspx?space=1&num=1770
假设有可行解
根据所给最短路的情况进行分类 枚举两点最短路
假设最短路是dist(i,j) 相连情况为 k(i,j)(-1表示没有直接相连，0表示相连了值为0,1表示相连了值为1）
1, dist(i,j)>1||dist(j,i)>1 --> k(i,j)==k(j,i)==-1.
2, dist(i,j)==1&&dist(j,i)==1 -->k(i,j)==k(j,i)==-1.
3, dist(i,j)==0&&dist(j,i)==0 -->k(i,j) k(j,i) 可以都等于0
4, dist(i,j)==1&&dist(j,i)==0 -->k(i,j) 可以等于1, k(j,i) 可以等于0.
4, dist(i,j)==0&&dist(j,i)==1 -->k(i,j) 可以等于0,k(j,i)可以等于1.
然后根据 k() 的情况 进行 floyd 看是否可以得到 dist()
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<stack>
#include<set>
#include<map>
#include<queue>
#include<deque>
#include<algorithm>
#include<cmath>
#define LL long long
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
const double PI=acos(-1.0);
const int N=305;
int a[N][N],b[N][N];
int ans[N][N];
int main()
{
//freopen("data.in","r",stdin);
int n;
cin>>n;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
cin>>a[i][j];
for(int i=1;i<=n;++i)
{
ans[i][i]=-1;
for(int j=i+1;j<=n;++j)
{
if(a[i][j]>1||a[j][i]>1)
ans[i][j]=ans[j][i]=-1;
else if(a[i][j]==1&&a[j][i]==1)
ans[i][j]=ans[j][i]=-1;
else if(a[i][j]==0&&a[j][i]==0)
ans[i][j]=ans[j][i]=0;
else if(a[i][j]==0&&a[j][i]==1)
{ans[i][j]=0;ans[j][i]=1;}
else if(a[i][j]==1&&a[j][i]==0)
{ans[i][j]=1;ans[j][i]=0;}
}
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(i==j)
b[i][j]=0;
else
b[i][j]=ans[i][j];
for(int l=1;l<=n;++l)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(b[i][l]!=-1&&b[l][j]!=-1&&(b[i][j]==-1||b[i][j]>b[i][l]+b[l][j]))
b[i][j]=b[i][l]+b[l][j];
bool blag=true;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(a[i][j]!=b[i][j])
blag=false;
if(!blag)
cout<<"NO"<<endl;
else
{
cout<<"YES"<<endl;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
cout<<(ans[i][j]+1);
cout<<endl;
}
}
return 0;
}