记录编号	127367	评测结果	AAAAAAAAAA
题目名称	城市规划	最终得分	100
用户昵称	乌龙猹	是否通过	通过
代码语言	C++	运行时间	0.037 s
提交时间	2014-10-15 16:24:40	内存使用	0.42 MiB

#include<iostream>
#include<cstdio>
using namespace std;
int n;
int dx[110][110],f[110][110];
bool v[110][110];
long long Ans=0;
int main()
{
	freopen("cityroad.in","r",stdin);
	freopen("cityroad.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=n;++j)
		{
			scanf("%d",&dx[i][j]);
			if(dx[i][j]<=0) dx[i][j]=0x7f7f7f7f/2;
			f[i][j]=0x7f7f7f7f;
		}
	}
	for(int k=1;k<=n;++k)
	{
		for(int i=1;i<=n;++i)
		{
			for(int j=1;j<=n;++j)
			{
				if(i!=j&&j!=k&&i!=k&&dx[i][k]+dx[k][j]<dx[i][j])
				{
					dx[i][j]=dx[i][k]+dx[k][j];
				}
			}
		}
	}
	for(int k=1;k<=n;++k)
	{
		for(int i=1;i<=n;++i)
		{
			for(int j=1;j<=n;++j)
			{
				if(i!=j&&j!=k&&i!=k&&dx[i][k]+dx[k][j]<f[i][j])
				{
					f[i][j]=dx[i][k]+dx[k][j];
				}
			}
		}
	}
	for(int i=1;i<=n;++i)
	{
		v[i][i]=0;
		for(int j=1;j<=n;++j)
		{
			if(i!=j&&f[i][j]>dx[i][j])
			{
				v[i][j]=1;
				Ans+=dx[i][j];
			}
		}
	}
	Ans/=2;
	printf("%d\n",Ans);
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<n;++j) printf("%d ",v[i][j]);
		printf("%d\n",v[i][n]);
	}
	return 0;
}