题目分析

单源最短路径问题要求我们找到从一个起点出发到图中所有其他点的最短路径。给定一个有向图，图中的边有权值，我们需要输出从起点到每个点的最短距离。

这个问题在计算机科学中有广泛的应用，比如网络路由、地图导航等。解决这个问题的经典算法包括 Dijkstra 算法、SPFA 算法等。由于题目中提到 SPFA 可能不通过某些构造数据，我们选择 Dijkstra 算法来解决这个问题。

算法原理

Dijkstra 算法是一种贪心算法，它通过每次选择当前距离起点最近的节点，并更新其相邻节点的距离来逐步找到最短路径。具体步骤如下：

初始化：将所有节点的距离设为无穷大，除了起点的距离设为 0。

使用优先队列（最小堆）存储节点及其到起点的距离，按距离从小到大排序。

每次从优先队列中取出距离最小的节点，遍历其所有相邻节点。如果通过当前节点到达相邻节点的距离比已知距离更短，则更新相邻节点的距离，并将其加入优先队列。

重复上述过程，直到优先队列为空。

Code

代码都写注释了，不懂的看注释。

ps: 弱化版（P3371）也能过

#include <bits/stdc++.h> // 万能的万能头
#define bp emplace_back // 简化代码，用 bp 代替 emplace_back
using namespace std; // 命名空间
const int N = 1e5 + 5; // 最大
const long long INF = LONG_LONG_MAX; // INF为long long最大值，表示不可达

int n, m, s; // n（节点数）、m（边数）、s（起点）
long long dis[N]; // 存储从起点到每个节点的最短距离
vector<pair<int, int>> adj[N]; // 邻接表，存储图的结构，pair中的第一个元素是目标节点，第二个元素是边的权重

// Dijkstra算法实现函数
void di() {
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq; // 定义优先队列pq，按距离从小到大排序
    fill(dis, dis + n + 1, INF); // 将dis初始化为INF
    dis[s] = 0; // 起点的距离初始化为0
    pq.push({0, s}); // 将起点加入优先队列

    while (!pq.empty()) { // 当优先队列不为空时，循环继续
        auto [d, u] = pq.top(); // 取出距离最小的节点u及其距离d
        pq.pop(); // 将该节点从优先队列中移除

        if (d > dis[u]) continue; // 如果当前距离大于已知最短距离，跳过该节点

        for (auto [v, w] : adj[u]) { // 遍历节点u的所有相邻节点v及其边权重w
            if (dis[v] > dis[u] + w) { // 如果通过u到达v的距离更短
                dis[v] = dis[u] + w; // 更新v的最短距离
                pq.push({dis[v], v}); // 将v及其新距离加入优先队列
            }
        }
    }
}

int main() {
    // 输入
    scanf("%d%d%d", &n, &m, &s); 
    for (int i = 0; i < m; i++) { 
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w); // 起点u、终点v、权重w
        adj[u].bp(v, w); // 添加到邻接表
    }

    di(); // 调用函数

    // 输出
    for (int i = 1; i <= n; i++) { // 循环
        if (dis[i] == INF) // 判断是否可达
            printf("%lld ", 2147483647); // 输出 INT_MAX
        else
            printf("%lld ", dis[i]); // 输出实际距离
    }

    return 0; // 完 结
}