记录编号 |
49249 |
评测结果 |
AAAAA |
题目名称 |
最难的任务 |
最终得分 |
100 |
用户昵称 |
Truth.Cirno |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
0.225 s |
提交时间 |
2012-11-07 15:37:09 |
内存使用 |
0.52 MiB |
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <memory.h>
#include <queue>
using namespace std;
int waynum[210],wayto[210][210],waycost[210][210],mincost[210];
bool inque[210];
queue<int> que;
int main(void)
{
freopen("hardest.in","r",stdin);
freopen("hardest.out","w",stdout);
int times,i,T,n,m,a,b,c;
cin>>T;
for (times=1;times<=T;times++)
{
memset(waynum,0,sizeof(waynum));
memset(wayto,0,sizeof(wayto));
memset(waycost,0,sizeof(waycost));
cin>>n>>m;
for (i=1;i<=n;i++)
mincost[i]=1000000000;
for (i=1;i<=m;i++)
{
cin>>a>>b>>c;
wayto[a][waynum[a]]=b;
wayto[b][waynum[b]]=a;
waycost[a][waynum[a]]=c;
waycost[b][waynum[b]]=c;
waynum[a]++;
waynum[b]++;
}
mincost[1]=0;
que.push(1);
inque[1]=true;
while (!que.empty())
{
a=que.front();
for (i=0;i<waynum[a];i++)
{
b=wayto[a][i];
c=waycost[a][i];
if (mincost[b]>mincost[a]+c)
{
mincost[b]=mincost[a]+c;
if (!inque[b])
{
que.push(b);
inque[b]=true;
}
}
}
que.pop();
inque[a]=false;
}
if (mincost[n]!=1000000000)
cout<<mincost[n]<<endl;
else
cout<<"-1\n";
}
return(0);
}