# 【最短路】Dijkstra## 题目描述给定一个 $n$ 个点$m$ 条有向边的带非负权图请你计算从 $s$ 出发到每个点的距离。数据保证你能从 $s$ 出发到任意点。## 输入格式第一行为三个正整数 $n m s$。第二行起 $m$ 行每行三个非负整数 $u_i v_i w_i$表示从 $u_i$ 到 $v_i$ 有一条权值为 $w_i$ 的有向边。## 输出格式输出一行 $n$ 个空格分隔

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 200010, M = 2 * N;

int head[N], ver[M], e[M], ne[M], idx;
int dist[N];
bool st[N];
int n, m, s;

void add(int a, int b, int c)
{
    ver[idx] = b, e[idx] = c, ne[idx] = head[a], head[a] = idx ++;
}

void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;
    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        st[t] = true;
        for (int j = head[t]; ~j; j = ne[j])
        {
            int k = ver[j];
            if (dist[k] > dist[t] + e[j])
                dist[k] = dist[t] + e[j];
        }
    }
}

int main()
{
    memset(head, -1, sizeof head);
    cin >> n >> m >> s;
    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    dijkstra();
    for (int i = 1; i <= n; i ++ ) cout << dist[i] << ' ';
    return 0;
}