http://poj.org/problem?id=3255
bessie 有时会去拜访她的朋友，但是她不想走最快回家的那条路，而是想走一条比最短的路长的次短路。
城镇由R条双向路组成，有N个路口。标号为1到N,问1号路口到N号路口的次短路长度是多少？次短路是
比最短路长度长的次短的路径。同一条边可以经过多次。
到某个顶点v的次短路要么帅到其他顶点u的最短路在加上u-v的边，要么是到u的次短路再加上u-v的边，
因此所需要求的就是到所有顶点的最短路和次短路，因此，对于每个顶点，我们记录的不仅仅是最短距离，
还有次短的距离，接下去只要用dijkstra算法相同的做法，不断更新这两个距离就能求出次短路了。
/* ***********************************************
Author : zch
Created Time :2015/5/13 8:16:45
File Name :a.cpp
************************************************ */ #include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
const int maxn = ;
const int INF = ; int N, R;
struct edge {
int to,cost;
edge() {}
edge(int x,int y) {
to=x;
cost=y;
}
};
typedef pair<int,int>P;
vector<edge>G[maxn];
int dist[maxn];
int dist2[maxn]; void dijkstra(int s) {
priority_queue<P,vector<P>,greater<P> >que;
for(int i=;i<=N;i++) dist[i]=INF;
for(int i=;i<=N;i++) dist2[i]=INF;
dist[s]=;
que.push(P(,s)); while(!que.empty()) {
P p=que.top(); que.pop();
int v=p.second, d=p.first;
if(dist2[v]<d) continue; //v的次短距离比d还小
for(int i=;i<G[v].size();++i) {
edge e=G[v][i];
//cout<<e.to<<endl;
int d2=d+e.cost;
if(dist[e.to]>d2) { //更新 最短距离
swap(dist[e.to],d2);
que.push(P(dist[e.to],e.to));
}
if(dist2[e.to]>d2&&dist[e.to]<d2) { //更新次短距离
dist2[e.to]=d2;
//cout<<d2<<endl;
que.push(P(dist2[e.to],e.to));
}
}
}
printf("%d\n",dist2[N]);
}
int main()
{
//freopen("a.txt","r",stdin);
//freopen("b.txt","w",stdout);
int a,b,c;
scanf("%d%d",&N,&R);
for(int i=;i<R;++i) {
scanf("%d%d%d",&a,&b,&c);
G[a].push_back(edge(b,c));
G[b].push_back(edge(a,c));
}
dijkstra();
return ;
}