记录编号	170555	评测结果	WWEEE
题目名称	最难的任务	最终得分	0
用户昵称	胡嘉兴	是否通过	未通过
代码语言	C	运行时间	0.245 s
提交时间	2015-07-14 11:35:22	内存使用	0.32 MiB

#include<stdio.h>
#include<math.h>
#include<ctype.h>
#include<stdlib.h>
#include<string.h>
#define N 200
int main()
{ 
	int dp[N][N], k, i, j, n, m, x, y, z, t;
	freopen("hardest.in", "r", stdin);
	freopen("hardest.out", "w", stdout);
	scanf("%d", &t);
	while(t--)
	{
		scanf("%d%d", &n, &m);
		for(i = 1; i <= n; i++)
		{
			for(j = 1; j <= n; j++)
			{
				if(i == j)
				{
					dp[i][j] = 0;
				}
				else
				{
					dp[i][j] = -1;
				}
			}
		}
		for(i = 1; i <= m; i++)
		{
			scanf("%d%d%d", &x, &y, &z);
			dp[x][y] = z;
			dp[y][x] = z;
		}
		for(k = 1; k <= n; k++)
		{
			for(i = 1; i <= n; i++)
			{
				for(j = 1; j <= n; j++)
				{
					if(dp[i][j] > dp[i][k] + dp[k][j])
					{
						dp[i][j] = dp[i][k] + dp[i][j];
					}
				}
			}
		}
		if(dp[1][i - 1] != -1)
		{
			printf("%d\n", dp[1][i - 1]);
		}
		else
		{
			printf("-1\n");
		}
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}