Roadblocks POJ - 3255【次最短路】

  求到某个点 $v$v 的次最短路，可认为是到某点 $u$u 的最短路，加上 $u\to v$u→v 的距离。和最短路的定义相同，因此可以借助于最短路来求解。

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
const int N=5e3+5;
const ll inf=0x3f3f3f3f;
typedef pair<ll,int> P;
priority_queue<P,vector<P>,greater<P> >que;
vector<P>pic[N];
ll dis[N],dis2[N];
void dij(int n)
{
    fill(dis+1,dis+1+n,inf);
    fill(dis2+1,dis2+1+n,inf);
    while(!que.empty())
        que.pop();
    que.push(make_pair(0,1));
    dis[1]=0;//只对dis[1]赋0，不能对dis2[1]赋0
    while(!que.empty())
    {
        P now=que.top();
        que.pop();
        if(dis2[now.second]<now.first)//表示已经用过该点更新过其他点的最短路和次最短路
            continue;
        for(int i=0;i<pic[now.second].size();i++)
        {
            P t=pic[now.second][i];
            ll d=now.first+t.first;
            if(d<dis[t.second])
            {
                swap(d,dis[t.second]);
                que.push(make_pair(dis[t.second],t.second));
            }
            if(d>dis[t.second]&&d<dis2[t.second])//比最短路大，但是可以更新次短路
            {
                dis2[t.second]=d;
                que.push(make_pair(dis2[t.second],t.second));
            }
        }
    }
}
int main()
{
    int n,r,v,u;
    ll w;
    while(scanf("%d%d",&n,&r)!=EOF)
    {
        for(int i=1;i<=n;i++)
            pic[i].clear();
        for(int i=1;i<=r;i++)
        {
            scanf("%d%d%lld",&u,&v,&w);
            pic[u].push_back(make_pair(w,v));
            pic[v].push_back(make_pair(w,u));
        }
        dij(n);
        printf("%d\n",dis2[n]);
    }
    return 0;
}