记录编号	69992	评测结果	AAAAAAAAAAA
题目名称	[福州培训2010] 最短路	最终得分	100
用户昵称	raywzy	是否通过	通过
代码语言	C++	运行时间	0.028 s
提交时间	2013-09-22 20:36:07	内存使用	0.35 MiB

#include<fstream>
using namespace std;
ifstream fin("shorta.in");
ofstream fout("shorta.out");
int f[101][101];
int N,M;
int main()
{
	int i,j,k;
	int A,B,C;
	fin>>N>>M;
	for(i=1;i<=N;i++)
		for(j=1;j<=N;j++)
			if(i!=j)
				f[i][j]=99999999;
	for(i=1;i<=M;i++)
	{
		fin>>A>>B>>C;
		f[A][B]=C;
		f[B][A]=C;
	}
	for(k=1;k<=N;k++)
		for(i=1;i<=N;i++)
			for(j=1;j<=N;j++)
			{
				if(f[i][k]+f[k][j]<f[i][j])
					f[i][j]=f[i][k]+f[k][j];
			}
	for(i=1;i<=N;i++)
	{
		for(j=1;j<=N;j++)
		{
			fout<<f[i][j]<<' ';
		}
		fout<<endl;
	}
	return 0;
}