POJ 3255 Roadblocks

链接：http://poj.org/problem?id=3255

题目要求1~N的次短路径. 

代码来自《挑战程序设计竞赛》

#include <iostream>
#include<queue>
#include<vector>
#define MAX_N 100005
#define INF 1000000
using namespace std;
struct edge
{
    int to;
    int cost;
};
typedef pair<int ,int> P;
vector<edge> g[MAX_N];
int dist1 [MAX_N];
int dist2 [MAX_N];
priority_queue<P,vector<P>,greater<P> > que;



void solve(int N)
{
    int i;
    for(i=0;i<MAX_N;i++)
    {
        dist1[i]=INF;
        dist2[i]=INF;
    }
    dist1[0]=0;
    que.push(make_pair(0,1));
    while(!que.empty())
    {
        P p=que.top();
        que.pop();
        int v=p.second,d=p.first;
        if(dist2[v]<d)
            continue;
        for(i=0; i<g[v].size(); i++)
        {
            edge &e=g[v][i];
            int d2=d+e.cost;
            if(dist1[e.to]>d2)
            {
                swap(dist1[e.to],d2);
                que.push(make_pair(dist1[e.to],e.to));
            }
            if(dist2[e.to]>d2&&dist1[e.to]<d2)
            {
                dist2[e.to]=d2;
                que.push(make_pair(dist2[e.to],e.to));
            }

        }

    }
    cout<<dist2[N]<<endl;


}

int main()
{
    int N,R;
    int ta,tb,tc;
    int i;
    edge e;
    cin>>N>>R;
    for(i=0;i<R;i++)
    {
        cin>>ta>>tb>>tc;
        e.to=tb;e.cost=tc;
        g[ta].push_back(e);
        e.to=ta;
        g[tb].push_back(e);
    }
    solve(N);

    return 0;
}