2015
07-16

# Shortest path

There are N cities (marked by 1, 2, …, N) and M bidirectional roads in the kingdom. There may be several roads between any two cities, but there is not any road connects the same city.
Your task is to find a shortest path from city 1 to city N, and the lengths of the edges you passed by must be strictly in increasing order.

There is an integer T (1 <= T <= 500) in the first line, indicates that there are T test cases in total.
For each test case, there are two integers N (2 <= N <= 10000) and M (1 <= M <= 50000), which have the same meaning as above. Then there are M lines, and there are three integers x (1 <= x <= N), y (1 <= y <= N), and z (1 <= z <= 10000000) in each line, indicate there is a bidirectional road between city x and city y.
There are at most ten test cases that satisfy that N > 200 or M > 1000.

There is an integer T (1 <= T <= 500) in the first line, indicates that there are T test cases in total.
For each test case, there are two integers N (2 <= N <= 10000) and M (1 <= M <= 50000), which have the same meaning as above. Then there are M lines, and there are three integers x (1 <= x <= N), y (1 <= y <= N), and z (1 <= z <= 10000000) in each line, indicate there is a bidirectional road between city x and city y.
There are at most ten test cases that satisfy that N > 200 or M > 1000.

4
4 6
1 2 1
1 2 2
2 3 3
2 3 1
3 4 2
4 3 6
3 2
1 2 1
2 3 1
3 1
1 2 1
2 2
2 1 1
1 2 2

10
1

3
5 5
1 2 1
2 3 2
3 4 3
1 4 4
4 5 4
5 5
1 2 2
2 3 3
3 4 4
1 4 5
4 5 5
5 5
1 2 2
2 3 3
3 4 4
1 4 5
4 5 6

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#include <stack>
#include <iostream>
using namespace std;
#define LL long long
const int N = 10009;
const int M = 100009;
const LL INF = 0x3f3f3f3f3f3f3f3f;
int f,t,dis;
return dis<t.dis;
}
} ld[M];
int n,m;
int fa[N];
LL dis[N];
int v[N];
LL vdis[N];
void oper(int st,int len)
{
int cnt=  0,l,r,d;
for(int i=0;i<len;i++)
{
l = ld[i+st].f,r= ld[st+i].t,d = ld[st+i].dis;
if(fa[l]&&dis[r]>d+dis[l])
{
v[cnt] = r;
vdis[cnt]= d+dis[l];
cnt++;
}
if(fa[r]&&dis[l]>d+dis[r])
{
v[cnt] = l;
vdis[cnt] = d+dis[r];
cnt++;
}
}
for(int i=0;i<cnt;i++)
{
dis[v[i]] = min(dis[v[i]],vdis[i]);
fa[v[i]] = 1;
}
}
void solve()
{
memset(fa,0,sizeof(fa));
for(int i=0;i<=n;i++) dis[i] = INF;
dis[1] = 0;
fa[1] = 1;
for(int i=0;i<m;)
{
int j;
for(j=i+1;j<m;j++)
{
if(ld[j].dis!=ld[i].dis) break;
}
oper(i,j-i);
i = j;
}
if(dis[n]!=INF)
cout<<dis[n]<<endl;
}
int main()
{
freopen("in.txt","r",stdin);
int cas;
scanf("%d",&cas);
while(cas--)
{
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
scanf("%d%d%d",&ld[i].f,&ld[i].t,&ld[i].dis);
sort(ld,ld+m);
solve();
}
return 0;
}