题目大意:

Input

第一行是一个整数T ( T ≤ 100 ),表示测试用例的个数。

每个测试用例的第一行是两个整数 n 和 m ( 1 ≤ n ≤ 200 , 0 ≤ m ≤ 10000 ),分别表示交汇点的个数以及路的条数。

接下来的m行都有3个整数 i, j, k,表示在城市i 和城市j 之间有一条长度为k的路。

假设交汇点从1到n编号。你的出发点是1,目的地是n。

道路都是双向的。

Output

每个测试用例输出一行,一个整数:逃跑的最短距离。如果无路可逃,输出-1。

Sample Input

1
2 1
1 2 3

Sample Output

3

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define P pair<int,int>
#define mp(i,j) make_pair(i,j)
using namespace std;
struct NODE { int to,co; };
int a[][];
int dis[],flag[];
int main()
{
int t;
while(~scanf("%d",&t)) {
while(t--) {
int n,m; scanf("%d%d",&n,&m);
memset(a,INF,sizeof(a));
while(m--) {
int u,v,w; scanf("%d%d%d",&u,&v,&w);
a[u][v]=a[v][u]=min(a[u][v],w);
}
memset(dis,INF,sizeof(dis));
memset(flag,,sizeof(flag));
queue <P> q;
q.push(mp(,)); dis[]=; flag[]=;
while(!q.empty()) {
P u=q.front(); q.pop();
flag[u.second]=; /// 出队 标为0
for(int i=;i<=n;i++) {
if(flag[i] || a[u.second][i]==INF)
continue; /// 已在队列内 或两点间不存在路径
if(dis[i]>u.first+a[u.second][i]) {
dis[i]=u.first+a[u.second][i];
flag[i]=; /// 入队 标为1
q.push(mp(dis[i],i));
} /// 更新最短路
}
}
if(dis[n]==INF) printf("-1\n");
else printf("%d\n",dis[n]);
}
} return ;
}
05-28 01:01