记录编号	16082	评测结果	AAAAAAAAAA
题目名称	429.城市规划	最终得分	100
用户昵称	lc	是否通过	通过
代码语言	C++	运行时间	0.123 s
提交时间	2010-04-19 15:36:50	内存使用	0.35 MiB

#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 103,Inf = 100000000;
int N,Ans;
int Dis[maxn][maxn],W[maxn][maxn];
bool T[maxn][maxn];


int min(int a,int b)
{
	return a<b?a:b;
}

void prep()
{
	scanf("%d",&N);
	for (int i=1; i<=N; i++)
		for (int j=1; j<=N; j++)
		{
			scanf("%d",&W[i][j]);
			Dis[i][j] = W[i][j]<=0?Inf : W[i][j];
		}
	for (int i=1; i<=N; i++) Dis[i][i] = 0;
}

bool Can(int x,int y)
{
	if (W[x][y]<=0) return false;
	bool Ok = false;
	for (int i=1; i<=N; i++)
	{
		if (Dis[i][x]+W[x][y]==Dis[i][y] || Dis[i][y]+W[y][x]==Dis[i][x])
		{
			Ok = true; break;
		}
	}
	if (!Ok) return false;
	for (int i=1; i<=N; i++)
	{
		if (i==x || i==y) continue;
		if (Dis[x][i]+Dis[i][y]==W[x][y])
			return false;
	}
	return true;
}

void work()
{
	for (int k=1; k<=N; k++)
		for (int i=1; i<=N; i++)
			for (int j=1; j<=N; j++)
			{
				if (k==i || k==j || i==j) continue;
				Dis[i][j] = min(Dis[i][j],Dis[i][k]+Dis[k][j]);
			}
	
	for (int i=1; i<N; i++)
		for (int j=i+1; j<=N; j++)
		{
			if (Can(i,j))
			{
				T[i][j] = T[j][i] = true;
				Ans += W[i][j];
			}
		}
	printf("%d\n",Ans);
	for (int i=1; i<=N; i++)
	{
		for (int j=1; j<N; j++)
			printf("%d ",T[i][j]);
		printf("%d\n",T[i][N]);
	}
}

int main()
{
	freopen("cityroad.in","r",stdin);
	freopen("cityroad.out","w",stdout);
	prep();
	work();
	return 0;
}