P4779 & P3371

题目理解

我们需要计算从指定的起点s到每个节点的最短路径。图是一个带有非负权值的有向图。图的节点数最多为10^5，边数最多为2 \times 10^5，权重可以非常大，所以需要用效率较高的算法来求解最短路径。

算法选择

考虑到图的规模和边的权重都可能较大（最多有2 \times 10^5条边），我们选择使用 Dijkstra 算法 来解决这个问题。Dijkstra 算法适用于带有非负权重的图，可以有效地求出从单一源点到其他点的最短路径。使用最小堆（优先队列）可以保证每次选择最短路径的节点，从而保证算法的时间复杂度是O((n + m) \log n)，符合题目的要求。

代码结构

1. 输入数据的处理：

   • 读取图的节点数n、边数m和起点s。
   • 读取每一条边的信息，边的信息包括起点、终点以及边的权重。

2. 初始化：

   • dist[] 数组用于存储从起点s到其他所有节点的最短距离，初始时所有节点的距离设为无穷大（代表尚未访问过），起点s的距离设为 0。
   • 使用邻接表 adj[] 存储图的结构。每个节点对应一个列表，存储该节点出发的所有边和边的权重。

3. 去重和处理边的更新：

   • 由于输入可能存在重复的边（同一对节点之间有多条边），所以在插入边时，我们使用一个检查机制：如果已经有一条从u到v的边，我们会保留权重最小的那一条。

4. Dijkstra 算法的实现：

   • 使用一个最小堆（优先队列）来实时选择当前距离最小的节点。
   • 对于每一个当前节点u，我们尝试更新它的邻接点v的最短路径，如果u到v的路径更短，就更新v的最短路径并将v加入堆中。

5. 输出结果：

   • 最后输出每个节点的最短路径。如果某个节点无法访问（距离仍然是无穷大），输出 inf 或类似标记。

代码注释

#include <algorithm>
#include <cstdint>
#include <functional>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

using ll = int64_t;
using std::cin, std::cout;

const ll maxn = 1e5+5;  // 最大节点数
ll n, m, s, dist[maxn], inf {(1ll<<31)-1};  // dist 用于存储最短路径，inf 表示无穷大
std::vector<std::pair<ll, ll>> adj[maxn];  // 邻接表，存储每个节点的出边 (终点, 权重)

// 主函数
int main(){
    // 读入数据
    std::iostream::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> m >> s;  // n: 节点数, m: 边数, s: 起点

    // 初始化距离数组，设置所有节点的距离为无穷大
    std::fill(dist, dist + 1 + n, inf);
    dist[s] = 0;  // 起点到自己的距离是 0

    // 读入图的边
    for (ll i = 1; i <= m; i++) {
        ll u, v, w;  // u: 起点, v: 终点, w: 边的权重
        cin >> u >> v >> w;
        
        // 处理重复边，保留权重最小的边
        for (auto& edge : adj[u]) {
            if (edge.first == v) {
                edge.second = std::min(edge.second, w);  // 如果已经有边 u->v，更新边权
                goto end;
            }
        }
        adj[u].emplace_back(v, w);  // 否则，插入新的边
        end:;
    }

    // 使用优先队列 (最小堆) 来实现 Dijkstra 算法
    std::priority_queue<std::pair<ll, ll>, std::vector<std::pair<ll, ll>>, std::greater<>> pq;
    pq.emplace(0, s);  // 将起点 s 和其距离 0 加入堆中

    // Dijkstra 算法主循环
    while (!pq.empty()) {
        auto [d, u] = pq.top();  // d: 当前节点的最短距离, u: 当前节点
        pq.pop();  // 弹出堆顶元素

        // 如果当前距离大于已知最短距离，说明这是一个无效的队列项，可以跳过
        if (d > dist[u]) continue;

        // 遍历 u 的所有邻接边
        for (auto& edge : adj[u]) {
            auto [v, w] = edge;  // v: 终点, w: 边的权重
            // 如果通过 u 到 v 的距离更短，更新 v 的最短距离
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.emplace(dist[v], v);  // 将更新后的 v 加入优先队列
            }
        }
    }

    // 输出最终的最短路径
    for (ll i = 1; i <= n; i++) {
        cout << dist[i] << ' ';  // 输出每个节点到起点的最短路径
    }
    cout << '\n';

    return 0;
}

代码关键点

1. 优先队列 (最小堆)：

   • std::priority_queue<std::pair<ll, ll>, std::vector<std::pair<ll, ll>>, std::greater<>> pq;
     这里我们使用最小堆来存储当前尚未处理的节点，并确保每次都能从堆中取出距离最小的节点。

2. 边的去重：

   • 在处理每条边时，使用 for (auto& edge : adj[u]) 检查是否已有相同的边。如果有，选择更新权重最小的边。

3. Dijkstra 算法的核心：

   • 通过优先队列逐步扩展最短路径，确保每次更新都是对当前节点的最短路径进行扩展。

时间复杂度

• 图的边数为m，节点数为n。
• 最小堆操作的时间复杂度是O(\log n)。
• 对于每条边，最多执行一次堆操作，因此时间复杂度是O((n + m) \log n)，可以处理最大限制。

总结

这段代码通过 Dijkstra 算法求解了从起点到所有节点的最短路径，使用了优先队列优化了算法的效率，能在较大的数据规模下有效运行。