oj1220
贝茜把家搬到了一个小农场，但她常常回到FJ的农场去拜访她的朋友。贝茜很喜欢路边的风景，不想那么快地结束她的旅途，于是她每次回农场，都会选择第二短的路径，而不象我们所习惯的那样，选择最短路。
贝茜所在的乡村有R(1<=R<=100,000)条双向道路，每条路都联结了所有的N(1<=N<=5000)个农场中的某两个。贝茜居住在农场1，她的朋友们居住在农场N（即贝茜每次旅行的目的地）。
贝茜选择的第二短的路径中，可以包含任何一条在最短路中出现的道路，并且，一条路可以重复走多次。当然咯，第二短路的长度必须严格大于最短路（可能有多条）的长度，但它的长度必须不大于所有除最短路外的路径的长度。
第二短路顾名思义要比第一短路要长，必剩余其他路短，所以比较是肯定要比较两次的啦，那么对于第二短路我们也要让它尽可能的短，所以我们用第一短路来寻找第二短路；
所以我们开两个数组，dis1，dis2，分别表示第一短路和第二短路；
所以
if(dis1[v]>dis1[x]+a[i].v)
{
dis2[v]=dis1[v];
dis1[v]=dis1[x]+a[i].v;
if(!vis[v]) vis[v]=1,q.push(v);
}
else if(dis1[x]+a[i].v<dis2[v]&&dis1[x]+a[i].v>dis1[v])
{//寻找满足条件的第二短路，二个条件是为了满足能够更新dis2（因为只有满足小于除最短路外的所有路）
dis2[v]=dis1[x]+a[i].v;
if(!vis[v]) q.push(v),vis[v]=1;
}
if(dis2[x]+a[i].v<dis2[v])
{//第二短路也需要找到最短路，比较更新；
dis2[v]=dis2[x]+a[i].v;
if(!vis[v]) q.push(v),vis[v]=1;
}
这样不断更新第二短路，就找到我们想要的answer啦；
代码
#include<bits/stdc++.h> using namespace std; #define N 5010 #define M 100010 int n,lin[N],tot,vis[N],dis1[N],xx,yy,vv,m,dis2[N]; inline int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*f; } struct gg { int y,next,v; }a[M<<1]; inline void init(int xx,int yy,int vv) { a[++tot].y=yy; a[tot].next=lin[xx]; a[tot].v=vv; lin[xx]=tot; } inline void spfa() { queue<int> q; memset(vis,0,sizeof(vis)); memset(dis1,127,sizeof(dis1)); memset(dis2,127,sizeof(dis2)); dis1[1]=0;vis[1]=1;q.push(1); while(!q.empty()) { int x=q.front();q.pop();vis[x]=0; for(int i=lin[x];i;i=a[i].next) { int v=a[i].y; if(dis1[v]>dis1[x]+a[i].v) { dis2[v]=dis1[v]; dis1[v]=dis1[x]+a[i].v; if(!vis[v]) vis[v]=1,q.push(v); } else if(dis1[x]+a[i].v<dis2[v]&&dis1[x]+a[i].v>dis1[v]) { dis2[v]=dis1[x]+a[i].v; if(!vis[v]) q.push(v),vis[v]=1; } if(dis2[x]+a[i].v<dis2[v]) { dis2[v]=dis2[x]+a[i].v; if(!vis[v]) q.push(v),vis[v]=1; } } } } int main() { n=read();m=read(); for(int i=1;i<=m;i++) { xx=read();yy=read();vv=read(); init(xx,yy,vv); init(yy,xx,vv); } spfa(); cout<<dis2[n]<<endl; return 0; }