c++ 迪杰斯特拉算法模板

好的，以下是 Dijkstra 算法的模板：

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int INF = 1e9;

struct Edge {
    int to, cost;
};

vector<Edge> G[MAXN];
int d[MAXN];

void dijkstra(int s) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que;
    fill(d, d + MAXN, INF);
    d[s] = 0;
    que.push(make_pair(0, s));

    while (!que.empty()) {
        pair<int, int> p = que.top();
        que.pop();

        int v = p.second;
        if (d[v] < p.first) continue;

        for (int i = 0; i < G[v].size(); i++) {
            Edge e = G[v][i];
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.push(make_pair(d[e.to], e.to));
            }
        }
    }
}

其中，MAXN 为节点个数的上限，INF 为一个足够大的值，将 d 数组初始化为 INF，表示源点到该点的最短距离尚未确定。dijkstra 函数的 s 参数表示源点。