C++dijkstra

Dijkstra算法是一种常见的图论算法，用于解决有权图中的单源最短路径问题。C++实现Dijkstra算法可以参考以下代码：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int INF = 0x3f3f3f3f;

struct Edge {
    int to, cost;
};

vector<Edge> G[MAXN];  // 图的邻接表存储
int d[MAXN];  // 存储起点到各个点的最短距离
bool vis[MAXN];  // 标记是否已经确定了最短路

void dijkstra(int s) {
    // 初始化
    memset(d, INF, sizeof(d));
    memset(vis, false, sizeof(vis));
    d[s] = 0;

    // 用优先队列维护未确定最短路的点
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, s));

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        if (vis[u]) continue;
        vis[u] = true;

        for (int i = 0; i < G[u].size(); i++) {
            int v = G[u][i].to;
            int cost = G[u][i].cost;

            if (!vis[v] && d[v] > d[u] + cost) {
                d[v] = d[u] + cost;
                pq.push(make_pair(d[v], v));
            }
        }
    }
}

其中，MAXN是存储最大节点数的常量。在图的邻接表中，每个元素表示一条从from到to的边，其权值为cost。函数dijkstra(s)可以计算出起点s到所有点的最短路径。