Problem Description
You are given a undirected graph with n nodes (numbered from 1 to n) and m edges. Alice and Bob are now trying to play a game.
Both of them will take different route from 1 to n (not necessary simple).
Alice always moves first and she is so clever that take one of the shortest path from 1 to n.
Now is the Bob’s turn. Help Bob to take possible shortest route from 1 to n.
There’s neither multiple edges nor self-loops.
Two paths S and T are considered different if and only if there is an integer i, so that the i-th edge of S is not the same as the i-th edge of T or one of them doesn’t exist.
Input
The first line of input contains an integer T(1 <= T <= 15), the number of test cases.
The first line of each test case contains 2 integers n, m (2 <= n, m <= 100000), number of nodes and number of edges. Each of the next m lines contains 3 integers a, b, w (1 <= a, b <= n, 1 <= w <= 1000000000), this means that there’s an edge between node a and node b and its length is w.
It is guaranteed that there is at least one path from 1 to n.
Sum of n over all test cases is less than 250000 and sum of m over all test cases is less than 350000.
Output
For each test case print length of valid shortest path in one line.
Sample Input
2
3 3
1 2 1
2 3 4
1 3 3
2 1
1 2 1
Sample Output
5
3
Hint
For testcase 1, Alice take path 1 - 3 and its length is 3, and then Bob will take path 1 - 2 - 3 and its length is 5.
For testcase 2, Bob will take route 1 - 2 - 1 - 2 and its length is 3
分析：
这道题又和Tyvj1293不一样了，
我们必须找到一条最短路，因此每条路可以重复走
我一开始非常simple，认为如果只有一条路可以到达终点
那次短路就是dis[t]*3 （到达终点–回来–再次到达终点）
后来发现不是这么简单的，
那我们把最短路中的最短一条边重复走三遍不就行了吗
但是这样我们也可以hack掉：
那怎么办呢
我们不光要套一个次短路模板
同时还要再加一个特判，
找到与最短路径上的点有关的路径中最短的一条边，
重复走这条边就可以了
tip
做题的时候还是要多思考，
找到复杂的样例，从中探寻规律
这里写代码片
#include<cstdio>
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
const ll INF=1e16;
const int N=100010;
int q[N<<1],tou,wei,n,m,st[N],tot,pre[N],s,t;
struct node{
int x,y,nxt;
ll v;
};
node way[N*6];
ll dis[N],ans1,ans2;
bool p[N];
void add(int u,int w,int z)
{
tot++;
way[tot].x=u;way[tot].y=w;way[tot].v=(ll)z;way[tot].nxt=st[u];st[u]=tot;
tot++;
way[tot].x=w;way[tot].y=u;way[tot].v=(ll)z;way[tot].nxt=st[w];st[w]=tot;
}
ll spfa(int s,int t)
{
for (int i=1;i<=n;i++) dis[i]=INF,p[i]=1,pre[i]=0;
wei=tou=0;
q[++wei]=s;
dis[s]=0, p[s]=0;
do
{
int r=q[++tou];
for (int i=st[r];i;i=way[i].nxt)
if (dis[way[i].y]>dis[r]+way[i].v)
{
dis[way[i].y]=dis[r]+way[i].v;
pre[way[i].y]=i;
if (p[way[i].y])
{
p[way[i].y]=0;
q[++wei]=way[i].y;
}
}
p[r]=1;
}
while (tou<wei);
return dis[t];
}
ll spfa2(int s,int t)
{
for (int i=1;i<=n;i++) dis[i]=INF,p[i]=1;
wei=tou=0;
q[++wei]=s;
dis[s]=0, p[s]=0;
do
{
int r=q[++tou];
for (int i=st[r];i;i=way[i].nxt)
if (dis[way[i].y]>dis[r]+way[i].v)
{
dis[way[i].y]=dis[r]+way[i].v;
if (p[way[i].y])
{
p[way[i].y]=0;
q[++wei]=way[i].y;
}
}
p[r]=1;
}
while (tou<wei);
return dis[t];
}
int main()
{
int T;
scanf("%d",&T);
while (T--)
{
memset(st,0,sizeof(st));
tot=0;
scanf("%d%d",&n,&m);
s=1; t=n;
for (int i=1;i<=m;i++)
{
int u,w,z;
scanf("%d%d%d",&u,&w,&z);
add(u,w,z);
}
ans1=spfa(s,t);
ans2=INF;
ll o=INF;
for (int i=t;i!=s;i=way[pre[i]].x)
{
ll u=way[pre[i]].v;
if (u<o) o=u;
way[pre[i]].v=INF;
ll an=spfa2(s,t);
if (an<ans2&&an!=ans1) ans2=an;
way[pre[i]].v=u;
if (way[pre[i]].x!=0)
for (int j=st[way[pre[i]].x];j;j=way[j].nxt)
if (way[j].v<o) o=way[j].v;
}
for (int j=st[t];j;j=way[j].nxt)
if (way[j].v<o) o=way[j].v;
if (ans1+2*o<ans2) ans2=ans1+2*o;
printf("%lld
",ans2);
}
return 0;
}