算法题：单源最短路径

问题描述

给定一个 $n$ 个点，$m$ 条有向边的带非负权图，请你计算从 $s$ 出发，到每个点的距离。

数据保证你能从 $s$ 出发到任意点。

输入格式

第一行为三个正整数 $n, m, s$。
第二行起 $m$ 行，每行三个非负整数 $u_i, v_i, w_i$，表示从 $u_i$ 到 $v_i$ 有一条权值为 $w_i$ 的有向边。

输出格式

输出一行 $n$ 个空格分隔的非负整数，表示 $s$ 到每个点的距离。

样例

输入

4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

输出

0 2 4 3

数据范围

$1 \leq n \leq 10^5$；

$1 \leq m \leq 2\times 10^5$；

$s = 1$；

$1 \leq u_i, v_i\leq n$；

$0 \leq w_i \leq 10 ^ 9$,

$0 \leq \sum w_i \leq 10 ^ 9$。

解决方案

思路

Dijkstra

代码

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

using namespace std;

const int N = 5e5 + 5;

struct Edge {
    int to;
    int next;
};

int n, m, s;
long long w[N], d[N];
int vis[N];

Edge e[N];
int head[N], count = 1;

void add(int a, int b, long long c) {
    e[count].to = b;
    e[count].next = head[a];
    head[a] = count;
    w[count] = c;

    ++count;
}

void dijkstra() {
    for (int i = 1; i <= n; ++i) {
        d[i] = INT32_MAX;
    }
    d[s] = 0;

    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;
    q.push({d[s], s});
    while (!q.empty()) {
        int x = q.top().second;
        q.pop();

        if (vis[x])
            continue;
        vis[x] = 1;

        for (int i = head[x]; i; i = e[i].next) {
            int y = e[i].to;
            if (d[y] > d[x] + w[i]) {   // 松弛操作
                d[y] = d[x] + w[i];
                q.push({d[y], y});
            }
        }
    }
}

int main() {
    cin >> n >> m >> s;
    for (int i = 0; i < m; ++i) {
        int a, b;
        long long c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    dijkstra();

    for (int i = 1; i <= n; ++i) {
        cout << d[i] << " ";
    }

    return 0;
}