单源最短路径模板

---

题目描述

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

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

输入格式

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

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

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$。

---

#include<bits/stdc++.h>
using namespace std;
const int N = 5 * 1e5 +5;
const int inf = INT_MAX;
int cnt = 0;
int dis[N], head[N], to[N], w[N], nxt[N];
bool vis[N];
int n, m, s;
struct node
{
    int v, w;
    friend bool operator < (node a, node b)
    {
        return a.w > b.w;
    }
};
node tmp;
priority_queue <node> q;
void addedge(int a, int b, int c)
{
    cnt++;
    to[cnt] = b;
    w[cnt] = c;
    nxt[cnt] = head[a];
    head[a] = cnt;
}
void dijkstra()
{
    for(int i = 1; i <= n; i++)
        dis[i] = inf;
    dis[s] = 0;
    tmp.v = s;
    tmp.w = 0;
    q.push(tmp);
    while(!q.empty())
    {
        int u = q.top().v;
        q.pop();
        if(vis[u])
            continue;
        vis[u] = 1;
        for(int i = head[u]; i; i = nxt[i])
        {
            if(dis[to[i]] > (long long)dis[u] + w[i])
            {
                dis[to[i]] = (long long)dis[u] + w[i];
                tmp.w = dis[to[i]];
                tmp.v = to[i];
                q.push(tmp);
            }
        }
    }
}
int main()
{
    scanf("%d%d%d", &n, &m, &s);
    for(int i = 1, u, v, t; i <= m; i++)
    {
        scanf("%d%d%d", &u, &v, &t);
        addedge(u, v, t);
    }
    dijkstra();
    for(int i = 1; i <= n; i++)
        printf("%d ", dis[i]);
    return 0;
}