记录编号	49209	评测结果	AAAAA
题目名称	最难的任务	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	1.432 s
提交时间	2012-11-07 15:02:33	内存使用	3.43 MiB

#include <fstream>
using namespace std;
ifstream cin("hardest.in");
ofstream cout("hardest.out");
int n,m,f[201][201],t;
void init()
{
	int i,a,b,c,j;
	cin>>n>>m;
	for (i=1;i<=n-1;i++)
	{
		f[i][i]=0;
		for (j=1;j<=n;j++) {f[i][j]=9999999;f[j][i]=9999999;}
	}f[n][n]=0;
	for (i=1;i<=m;i++)
	{
		cin>>a>>b>>c;
		if (c<f[a][b]) {f[a][b]=c;f[b][a]=c;}
	}
}
int main()
{
	int i,j,k,l;
	cin>>t;
	for (l=1;l<=t;l++)
	{
		init();
		for (k=1;k<=n;k++)
			for (i=1;i<=n;i++)
				for (j=1;j<=n;j++)
				{
					if (f[i][k]!=9999999&&f[k][j]!=9999999&&(i!=k&&i!=j&&k!=j))
					{
						if (f[i][k]+f[k][j]<f[i][j])
						{
							f[i][j]=f[i][k]+f[k][j];
							f[j][i]=f[i][k]+f[k][j];
						}
					}
				}
		if (f[1][n]!=9999999) cout<<f[1][n]<<endl;else cout<<-1<<endl;
	}
	return 0;
}