求次短路问题，方法类似于求单源最短路，不过本题是将单源最短路和次最短路一块求解

到某一点次最短路（eg：u）： 假设最短路为s->v->u , 次短路为 s->v->u‘ 或 s->v‘->u 注：s->v‘ 表示s->v 的次短路 ，v->u‘ 表示v->u 的次短路

需要做的就是同步更新单源最短路和次最短路

若当前节点为u,与u相邻节点为v

1、若与u相邻的节点v，通过u可以最小化s到其的距离，则更新其最短路，并记下原来s到v的最短路，以备更新次短路

2、 a、 若s通过u到v的路径长度大于s到v的最小路径长度，但是小于s到v的次短路长度，则更新s到v的次短路径

　　　b、　若是原来的最短路小于次短路，更新次短路

#include <iostream>#include <vector>#include <queue>#define maxn 100010#define INF 9999999999using namespace std;typedef pair<int,int>p;struct edge {    int from;    int to;    long long  cost;};int n,r;vector <edge> g[maxn];long long dist[maxn],dist2[maxn];void solve(){    priority_queue<p,vector<p>,greater<p> > que;    fill(dist,dist+n,INF);    fill(dist2,dist2+n,INF);    dist[0] = 0;    que.push(p(0,0));    while(!que.empty()){        p pp = que.top();        que.pop();        int v = pp.second;        int d = pp.first;        if (dist2[v] < d )            continue;        for (int i=0;i<g[v].size();i++){            edge &e = g[v][i];            int d2 = d+ e.cost;            if (dist[e.to] > d2){                int tp = dist[e.to];                dist[e.to] = d2;                d2 = tp;                que.push(p(dist[e.to],e.to));            }            if (dist2[e.to] > d2 && dist[e.to] <d2){                dist2[e.to]=d2;                que.push(p(dist2[e.to],e.to));            }        }    }    cout<< dist2[n-1]<<endl;}int main(){    cin>>n>>r;    edge tmp,tmp1;    int from,to,cost;    for(int i=0;i<r;i++){        cin>>from>>to>>cost;        //cout<<tmp.from<<tmp.to<<tmp.cost;        tmp.from = from -1;        tmp.to = to-1;        tmp.cost =cost;        g[from-1].push_back(tmp);        tmp1.from = to-1;        tmp1.to = from -1;        tmp1.cost = cost;        g[to-1].push_back(tmp1);    }    solve();    return 0;}