【正经题解】单源最短路径1

定义全局变量，包括结构体 $node$ 表示节点，结构体 $Edge$ 表示图的边，数组 $h$ 表示图的邻接表，数组 $e$ 存储边的信息，数组 $v$ 标记节点是否被访问过，数组 $d$ 存储起始点到各个点的最短距离。
定义函数 $add$ _ $edge$ 用于添加边到邻接表。
定义函数 $dijkstra$ 实现 $Dijkstra$ 算法，初始化距离数组，使用优先队列存储节点和距离信息，不断更新最短距离。
在主函数中，读取输入的点的个数 $n$ 、有向边的个数 $m$ 、出发点的编号 $s$ 。
读取 $m$ 行边的信息，调用 $add$ _ $edge$ 添加边到邻接表。
调用 $dijkstra$ 计算最短路径。
输出最短路径长度，若不能到达则输出 $-1$ 。

#include<bits/stdc++.h>
using namespace std;

const int N = 1010;

// 定义节点结构体
struct node {
    int var, val;
    friend bool operator<(node a, node b) {
        return a.val > b.val;
    }
};

// 定义边结构体
struct Edge {
    int to, dis, last;
} e[N];

int h[N], en, n, m, s, v[N], d[N];

// 添加边到邻接表
void add_edge(int from, int to, int dis) {
    e[++en].dis = dis;
    e[en].to = to;
    e[en].last = h[from];
    h[from] = en;
}

// Dijkstra算法
void dijkstra() {
    memset(d, 0x3f, sizeof d);
    d[s] = 0;
    priority_queue<node> q;
    q.push({s, d[s]});
    while (!q.empty()) {
        node head = q.top();
        q.pop();
        int t = head.var, dt = head.val;
        if (v[t]) continue;
        v[t] = 1;
        for (int j = h[t]; j != 0; j = e[j].last) {
            int to = e[j].to, dis = e[j].dis;
            if (!v[to]) {
                d[to] = min(d[to], dt + dis);
                q.push({to, d[to]});
            }
        }
    }
}

int main() {
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        add_edge(u, v, w);
    }
    dijkstra();
    for (int i = 1; i <= n; i++) {
        if (d[i] == 0x3f3f3f3f) cout << -1 << " ";
        else cout << d[i] << " ";
    }
    return 0;
}