POJ 3255 Roadblocks （Dijkstra求最短路径的变形）（Dijkstra求次短路径）

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <vector>
#include <queue> 
using namespace std;
typedef long long ll;
#define MAX_N 5010
#define INF 2147483647

typedef pair<int,int> P; //first是最短距离，second是顶点编号 

struct edge{
    int to,cost;
};

int n,r;   //顶点数，边数 
vector <edge> G[MAX_N]; //图的邻接表表示，G[x]表示点x相连的所有的边的集合 

int dist1[MAX_N];   //最短路径 
int dist2[MAX_N];   //次短路径 

void solve(){
    //通过指定greater<P>参数，堆按照first从小到大的顺序取出值。 
    priority_queue<P, vector<P>, greater<P> > que;
    fill(dist1, dist1+n, INF);
    fill(dist2, dist2+n, INF);
    dist1[0] = 0;
    que.push(P(0,0));
    
    
    while(!que.empty()){
        P p = que.top(); que.pop();
        int v = p.second, d = p.first;//取出编号和距离 
        
        //如果次短距离比之前加入这个点短，说明加入这个点之后又更新过
        //这里continue相当于一种剪枝，没有这句也不会错，但是加了效率会变高 
        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(dist1[e.to] > d2){
                swap(dist1[e.to] ,d2); //把之前的距离取出来，更新次短路径 
                que.push(P(dist1[e.to], e.to)) ;  // 把更新过的点加入队列，用这个点去更新其他点 
            }
            //如果d2没有更新过这个点的最短路径，就直接用d2更新次短路径
            //如果d2更新过这个点的最短路径，就用d2交换出来的值更新次短路径 
            if(dist2[e.to] > d2 && dist1[e.to] < d2){
                dist2[e.to] = d2;
                que.push(P(dist2[e.to], e.to));
            }
        }
    }
    printf("%d\n",dist2[n-1]);
} 

int main(){
    cin >> n >> r;
    int x,y,d;
    for(int i = 0;i < r; i++){
        edge e;
        cin >> x >> y >> d;
        e.cost = d;e.to = y-1;
        G[x-1].push_back(e);
        e.to = x-1;
        G[y-1].push_back(e);
    } 
    solve();
    return 0;
} 

POJ 3255 Roadblocks （Dijkstra求最短路径的变形）（Dijkstra求次短路径）

标签：nod   backtrack   time   section   describe   dir   include   指定   zhang