P3371 P4779

链式前向星存图

堆优化版 ：$O(mlogm)$

邻接表:

void solve() {
    int n, m, s;cin >> n >> m >> s;
    vector<pair<int, int>> g[n + 1];
    while (m--) {
        int u, v, w;cin >> u >> v >> w;
        g[u].push_back({v,w});
    }
    vector<int> dis(n + 1, INT_MAX), vis(n + 1);dis[s] = 0;
    priority_queue<pair<int, int>>q;q.push({0,s});
    while (q.size()) {
        auto [p, u] = q.top();q.pop();
        if (vis[u])continue;
        vis[u] = 1;
        for (auto [v, w] : g[u]) {
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;q.push({-dis[v],v});
            }
        }
    }
    for (int i = 1; i <= n; i++)
        cout << dis[i] << " ";
}

前向星:

#include <bits/stdc++.h>
using namespace std;
//#define int long long
int n, m, s;
struct
{
    int v, w, next;
} a[200010];
bool vis[100010];
int dis[100010];
int cnt = 1;
int head[100010];
void add(int u, int v, int w)//链式前向星存图
{
    a[cnt].w = w;
    a[cnt].v = v;
    a[cnt].next = head[u];
    head[u] = cnt++;
}
#define pll pair<int, int>
priority_queue<pll, vector<pll>, greater<pll>> q;
void dijkstra(int s) {
    memset(dis, 0x7f, sizeof dis);
    // for (int i = 1; i <= n; i++)
    //     dis[i] = INT_MAX;//弱化版还需要ll
    q.push({0, s});
    dis[s] = 0;
    while (!q.empty()) {
        pll t = q.top();
        q.pop();
        int u = t.second;
        if (vis[u])
            continue;
        vis[u] = true;
        for (int i = head[u]; i; i = a[i].next) {
            int v = a[i].v;
            if (dis[v] > dis[u] + a[i].w) {
                dis[v] = dis[u] + a[i].w;
                q.push({dis[v], v});
            }
        }
    }
}
int main() {
    cin >> n >> m >> s;
    while (m--) {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
    }
    dijkstra(s);
    for (int i = 1; i <= n; i++)
        cout << dis[i] << " ";
}