单源最短路径洛谷【P4779】

题目描述

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

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

输入格式

第一行为三个正整数 n,m,sn,m,s。第二行起 mm 行，每行三个非负整数 ui,vi,wiui,vi,wi，表示从 uiui 到 vivi 有一条权值为 wiwi 的有向边。

输出格式

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

输入输出样例

输入 #1

输出 #1

0 2 4 3

说明/提示

样例解释请参考数据随机的模板题。

1≤n≤1051≤n≤105；

1≤m≤2×1051≤m≤2×105；

s=1s=1；

1≤ui,vi≤n1≤ui,vi≤n；

0≤wi≤1090≤wi≤109,

0≤∑wi≤1090≤∑wi≤109。

代码解答：

cpp
#include <iostream>
#include <queue>
#include <cstdio>
#include <algorithm>
#include <limits>using namespace std;// 常量定义
const int INF = numeric_limits<int>::max();
const int MAX_NODES = 100010;    // 最大节点数
const int MAX_EDGES = 500010;    // 最大边数// 边的结构体
struct Edge {int destination, weight, next; // 目的节点、边的权重、下一条边的索引
};// 邻接表
Edge edges[MAX_EDGES];
int head[MAX_NODES], edgeCount = 0; // head 数组表示每个节点的邻接边链表，edgeCount 记录总边数// 向邻接表中添加一条边
void addEdge(int from, int to, int weight) {edges[++edgeCount].destination = to;edges[edgeCount].weight = weight;edges[edgeCount].next = head[from];head[from] = edgeCount;
}int numNodes, numEdges, source;
int distances[MAX_NODES]; // 保存从源点到每个节点的最短距离// 节点结构体，用于优先队列中的元素
struct Node {int id, distance;bool operator < (const Node &other) const {return distance > other.distance; // 小顶堆（距离小的优先）}
};// Dijkstra 算法
void dijkstra() {fill(distances, distances + numNodes + 1, INF); // 初始化所有距离为 INFdistances[source] = 0; // 源点到自己的距离为 0priority_queue<Node> pq; // 优先队列（最小堆）pq.push({source, 0});while (!pq.empty()) {Node current = pq.top();pq.pop();int u = current.id;int currentDistance = current.distance;if (currentDistance != distances[u]) continue; // 如果当前距离已经不是最短距离，则跳过// 遍历所有邻接边for (int i = head[u]; i; i = edges[i].next) {int v = edges[i].destination;int weight = edges[i].weight;// 如果通过 u 到达 v 的距离更短，则更新并加入优先队列if (distances[u] + weight < distances[v]) {distances[v] = distances[u] + weight;pq.push({v, distances[v]});}}}
}int main() {int from, to, weight;scanf("%d%d%d", &numNodes, &numEdges, &source); // 读取节点数、边数和源点for (int i = 1; i <= numEdges; i++) {scanf("%d%d%d", &from, &to, &weight); // 读取每条边的信息addEdge(from, to, weight);}dijkstra(); // 执行 Dijkstra 算法for (int i = 1; i <= numNodes; i++) {if (distances[i] == INF) {printf("INF ");} else {printf("%d ", distances[i]);}}return 0;
}

局部代码解析:

`const int INF = numeric_limits<int>::max()：`

在 C++ 中，const int INF = numeric_limits<int>::max(); 是用来定义一个表示“无穷大”的常量。这个常量通常用于图算法中，作为一种便捷的方式来表示一个节点到其他节点的距离是不可达的。下面是详细的解释：

`numeric_limits<int>::max()`

numeric_limits<int> 是 C++ 标准库中的一个模板类，用于提供有关 int 类型的信息。
max() 是 numeric_limits 类的一个静态成员函数，它返回该类型可以表示的最大值。

例如，对于 int 类型，numeric_limits<int>::max() 通常返回 2147483647（在大多数系统上），这表示 int 类型能够存储的最大整数值。

bool operator < (const Node &other) const：

在 C++ 中，operator< 的重载用于定义两个对象在特定条件下的大小关系。对于 Node 结构体，重载 < 运算符通常是为了在容器中如优先队列（std::priority_queue）或者集合（std::set）中确定元素的排序方式。

让我们详细分析 bool operator < (const Node &other) const 的重载在 Node 结构体中的用途：

cpp
struct Node {int id, distance;bool operator < (const Node &other) const {return distance > other.distance; // 实现小顶堆的排序}
};

作用

定义排序规则：
- 这个重载的 < 运算符定义了两个 Node 对象的比较方式。特别地，这个实现会影响数据结构如何对这些 Node 对象进行排序。
- 在标准的 std::priority_queue 中，元素是根据优先级（或排序标准）进行排列的。默认情况下，std::priority_queue 实现为大顶堆（即最大优先队列），即最大元素优先出队列。
小顶堆实现：
- 在 Node 结构体中，bool operator < (const Node &other) const { return distance > other.distance; } 实现了一个小顶堆（即最小优先队列）的排序规则。
- 具体来说，这行代码表示如果当前 Node 的 distance 大于 other 的 distance，那么当前 Node 被认为不小于 other。因此，具有较小 distance 的 Node 会有更高的优先级，被优先处理。

为什么要这么写？

优先队列的要求：
- std::priority_queue 默认是大顶堆。如果希望实现小顶堆，可以通过重载 < 运算符来改变排序规则。这是因为 std::priority_queue 是基于堆实现的，其中堆的性质是通过比较操作定义的。
小顶堆的实现：
- 小顶堆中的根节点是所有节点中 distance 最小的节点。为了让小顶堆的性质成立，较小的 distance 应该排在前面（即更高的优先级）。因此，通过将 distance > other.distance 用于比较，确保了距离较小的节点会优先于距离较大的节点。