记录编号	204354	评测结果	AAAAA
题目名称	最难的任务	最终得分	100
用户昵称	ミント	是否通过	通过
代码语言	C++	运行时间	0.688 s
提交时间	2015-11-04 10:57:56	内存使用	0.50 MiB

#include <fstream>
#include <algorithm>
#include <string>
#include <cstring>

using namespace std;

ifstream fin("hardest.in");
ofstream fout("hardest.out");

const int maxn = 200 + 20;
int n, m;
int map[maxn][maxn];

void floyd()
{
	memset(map, -1, sizeof(map));
	
	fin>>n>>m;
	
	if(n==1)
	{
		fout<<0<<endl;
		return ;
	}
	//建立邻接矩阵
	for(int i=1;i<=m;i++)
	{
		int a, b;
		int v;
		
		fin>>a>>b;
		fin>>v;
		if(map[a][b]==-1||map[a][b]>v)
		{
			map[a][b] = v;
			map[b][a] = v;
		}
	}//end for;
	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&&k!=i)
					if(map[i][k]!=-1&&map[k][j]!=-1)
						if(map[i][j]==-1||map[i][j]>map[i][k]+map[k][j])
							map[i][j] = map[i][k] + map[k][j];
	fout<<map[1][n]<<endl;
	return ;
}
int main()
{
	int t;
	
	fin>>t;
	for(int i=1;i<=t;i++)
		floyd();
	
	fin.close();
	fout.close();
	
	return 0;
}