Dijkstra 最短路

CSP-J · 编程模板 · 片段 · cpp · 难度 4/5 · 共 1228 字

非负权最短路，优先队列取最近未确定点

图论
最短路

前置内容

正文

// Dijkstra：非负权最短路
// 贪心选最近未确定点
// 用优先队列取最小距离
// 邻接表建图（见 cspj-adj）
#include <cstdio>
#include <queue>
using namespace std;
int h[10005], nxt[200005];
int to[200005], w[200005];
int cnt = 0, n, m, dis[10005];
bool vis[10005];
// 加边（带权）
void add(int u, int v, int c) {
    nxt[++cnt] = h[u];
    h[u] = cnt;
    to[cnt] = v;
    w[cnt] = c;
}
// 小根堆：存（距离, 点）
priority_queue<pair<int, int>,
    vector<pair<int, int> >,
    greater<pair<int, int> > > pq;
void dij(int s) {
    // 距离初为无穷大
    for (int i = 1; i <= n; i++)
        dis[i] = 1e9;
    dis[s] = 0;
    pq.push({0, s});
    while (!pq.empty()) {
        int u = pq.top().second; pq.pop();
        // 已确定过则跳过
        if (vis[u]) continue;
        vis[u] = 1;
        // 松弛所有出边
        for (int e = h[u]; e; e = nxt[e])
            // 更近则更新并入队
            if (dis[u] + w[e]
                < dis[to[e]]) {
                dis[to[e]] = dis[u]
                    + w[e];
                pq.push({dis[to[e]],
                    to[e]});
            }
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v, c;
        scanf("%d%d%d", &u, &v, &c);
        add(u, v, c);
    }
    dij(1);
    printf("%d", dis[n]);
    return 0;
}

Dijkstra 最短路

前置内容

正文

CSP-J · 编程模板的其它内容