Dijkstra算法实现次短路

Dijkstra可以用于求解最短路问题，实际上该算法也可以实现次短路，更一般的，该算法可以实现第k短路

模版

题目：POJ-3255

代码

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int MAX_N = 5001, INF = 0x7fffffff;
// 分别存放0号节点到该节点的最短距离、次短距离
int dist1[MAX_N], dist2[MAX_N];
int n, r;
struct Edge {
    int adj, cost;
    Edge(int adj, int cost) {this->adj = adj, this -> cost = cost;}
};
// 第一个代表距离、第二个代表后继节点
typedef pair<int, int> P;
vector<Edge> nodeEdges[MAX_N];
void addEdge(int u, int v, int cost) {
    nodeEdges[u].push_back(Edge(v, cost));
    nodeEdges[v].push_back(Edge(u, cost));
}
// Dijkstra 思想
void solve() { 
    // 距离小的P优先级高
    priority_queue<P, vector<P>, greater<P> > myQueue; 
    fill(dist1, dist1 + n, INF);
    fill(dist2, dist2 + n, INF);
    dist1[0] = 0;
    myQueue.push(P(0, 0));
    while (!myQueue.empty()) {
        P top = myQueue.top();
        myQueue.pop();
        int adjNode = top.second, dist = top.first;
        if (dist2[adjNode] < dist)continue;
        for (int i = 0;i < nodeEdges[adjNode].size();i++) {
            Edge edge = nodeEdges[adjNode][i];
            int toNodeDist = dist + edge.cost;
            // 更新最短距离
            if (toNodeDist < dist1[edge.adj]) {
                swap(dist1[edge.adj], toNodeDist);
                myQueue.push(P(dist1[edge.adj], edge.adj));
            }
            // 更新次短距离
            if (dist2[edge.adj] > toNodeDist && dist1[edge.adj] < toNodeDist) {
                dist2[edge.adj] = toNodeDist;
                myQueue.push(P(dist2[edge.adj], edge.adj));
            }
        }
    }
    printf("%d\n",dist2[n - 1]);
}
int main() {
    int u, v, w;
    scanf("%d%d", &n, &r);
    for (int i = 0; i < r; i++) {
        scanf("%d%d%d", &u, &v, &w);
        addEdge(u - 1, v - 1, w);
    }
    solve();
    return 0;
}