记录编号	49146	评测结果	AAAAA
题目名称	最难的任务	最终得分	100
用户昵称	ZYHAzwraith	是否通过	通过
代码语言	C++	运行时间	0.080 s
提交时间	2012-11-07 13:18:39	内存使用	3.31 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;

const int maxn = 200+5;
const int maxm = 10000;
const int inf = ~0U >> 2;

int T, n, m, u, v, w, map[maxn][maxn], dis[maxn];

void spfa()
{
    queue<int> q;   q.push(1);
    bool inq[maxn]; memset(inq, 0, sizeof(inq)); dis[1] = 0;
    while(!q.empty()) {
        int x = q.front(); q.pop();
        inq[x] = false;
        for(int i = 1; i <= n; i++) if(map[x][i] && dis[x]+map[x][i] < dis[i])
        {
            dis[i] = dis[x]+map[x][i];
            if(!inq[i]) { inq[i] = true; q.push(i); }
        }
    }
}

int main()
{
    freopen("hardest.in", "r", stdin);
    freopen("hardest.out", "w", stdout);
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &m);
        memset(map, 0, sizeof(map));
        for(int i = 1; i <= n; i++) dis[i] = inf;
        for(int i = 1; i <= m; i++) {
            scanf("%d%d%d", &u, &v, &w);
            if(map[u][v] && w >= map[u][v])    continue;
            map[u][v] = map[v][u] = w;
        }
        spfa();
        printf("%d\n", (dis[n] == inf ? -1: dis[n]));
    }
    return 0;
}