记录编号	125432	评测结果	AAAAA
题目名称	最难的任务	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.071 s
提交时间	2014-10-08 19:34:56	内存使用	0.69 MiB

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
queue<int> A;
int x,n,m,h=0,i,zj1,zj2,zj3,lin[210][210],quan[210][210];
bool qwq[210][210]={0};
long long zui[210]={0};
int main()
{
	freopen("hardest.in","r",stdin);
	freopen("hardest.out","w",stdout);
	scanf("%d",&x);
	while(x)
	{
		x--;
		h=0;
		scanf("%d%d",&n,&m);
		for(i=1;i<=n;i++) zui[i]=1e10;
		for(i=1;i<=m;i++)
		{
			scanf("%d%d%d",&zj1,&zj2,&zj3);
			lin[zj1][0]++;
			lin[zj1][ lin[zj1][0] ]=zj2;
			if(!qwq[zj1][zj2])
			{
				quan[zj1][zj2]=zj3;
				qwq[zj1][zj2]=true;
			}
			else
			if(zj3<quan[zj1][zj2])quan[zj1][zj2]=zj3;
			lin[zj2][0]++;
			lin[zj2][ lin[zj2][0] ]=zj1;
			if(!qwq[zj2][zj1])
			{
				quan[zj2][zj1]=zj3;
				qwq[zj2][zj1]=true;
			}
			else
			if(zj3<quan[zj2][zj1])quan[zj2][zj1]=zj3;
		}
		h=1;
		while(h<=lin[1][0])
		{
			A.push(lin[1][h]);
			zui[lin[1][h]]=quan[1][ lin[1][h] ];
			h++;
		}
		while(!A.empty())
		{
			zj1=A.front();
			A.pop();
			for(i=1;i<=lin[zj1][0];i++)
			{
				zj2=lin[zj1][i];
				if(zui[zj2]>zui[zj1]+quan[zj1][zj2])
				{
					A.push(zj2);
					zui[zj2]=zui[zj1]+quan[zj1][zj2];
				}
			}
		}
		if(n==1)printf("0\n");
		else
		{
			if(zui[n]==1e10)printf("-1\n");
			else printf("%lld\n",zui[n]);
		}
		memset(qwq,0,sizeof(qwq));
		memset(lin,0,sizeof(lin));
		memset(quan,0,sizeof(quan));
	}
	return 0;
}