46.Acwing基础课第850题-简单-Dijkstra求最短路Ⅱ
题目描述
给定一个 n个点 m条边的有向图，图中可能存在重边和自环，所有边权均为正值。
请你求出 1号点到 n号点的最短距离，如果无法从 1号点走到 n号点，则输出 −1。
输入格式
第一行包含整数 n和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x到点 y的有向边，边长为 z。
输出格式
输出一个整数，表示 1号点到 n号点的最短距离。
如果路径不存在，则输出 −1。
数据范围
\(1≤n,m≤1.5×10^5\),
\(图中涉及边长均不小于 0，且不超过 10000。\)
\(数据保证:如果最短路存在，则最短路的长度不超过 10^9。\)
输入样例：
3 3
1 2 2
2 3 1
1 3 4
输出样例：
3
代码：
#include <cstring> // 包含memset等内存操作函数
#include <iostream> // 标准输入输出
#include <algorithm> // 算法相关（此处主要用于优先队列的比较器）
#include <queue> // 优先队列（堆）的头文件using namespace std;// 定义Pair<int, int>为PII，第一个值存距离，第二个值存节点编号
typedef pair<int, int> PII;// 数据范围：节点数/边数最大1e6+10（适配题目1e5~1e6级别的数据）
const int N = 1e6 + 10;int n, m; // n：节点数，m：边数
// 邻接表存储结构：
// h[]: 每个节点的邻接表头指针（初始-1表示无邻边）
// w[]: 对应每条边的权值
// e[]: 对应每条边的终点节点
// ne[]: 下一条边的索引（链表结构）
// idx: 边的计数器（用于给每条边分配唯一索引）
int h[N], w[N], e[N], ne[N], idx;
int dist[N]; // dist[i]：起点(1号节点)到i号节点的最短距离（初始为无穷大）
bool st[N]; // st[i]：标记i号节点是否已确定最短距离（出堆后标记为true）// 邻接表加边函数：添加一条从a到b、权值为c的有向边
void add(int a, int b, int c)
{e[idx] = b; // 第idx条边的终点是bw[idx] = c; // 第idx条边的权值是cne[idx] = h[a];// 第idx条边的下一条边是原a节点的头指针指向的边h[a] = idx ++;// 更新a节点的头指针为当前边的索引，边计数器+1
}// 堆优化版Dijkstra算法：求1号节点到n号节点的最短距离
int dijkstra()
{// 初始化距离数组为0x3f3f3f3f（约1e9，代表无穷大，且加法不溢出）memset(dist, 0x3f, sizeof dist);dist[1] = 0; // 起点1号节点到自身的距离为0// 定义小根堆：优先队列存储PII（距离，节点编号），按距离从小到大弹出// greater<PII>：指定比较器为升序（默认大根堆，需手动改为小根堆）priority_queue<PII, vector<PII>, greater<PII>> heap;heap.push({0, 1}); // 起点入堆：距离0，节点1// 堆非空时循环（所有节点处理完则堆空）while (heap.size()){// 取出堆顶元素（当前距离最小的节点）auto t = heap.top();heap.pop(); // 弹出堆顶// 拆分堆顶元素：ver是节点编号，distance是当前记录的到该节点的距离int ver = t.second, distance = t.first;// 如果该节点已确定最短距离，直接跳过（堆中可能存重复节点，只处理第一次出堆的最小距离）if (st[ver]) continue;st[ver] = true; // 标记该节点已确定最短距离// 遍历ver节点的所有邻边（邻接表遍历）// i初始为ver的头指针，i!=-1表示还有下一条边，i=ne[i]遍历下一条边for (int i = h[ver]; i != -1; i = ne[i]){int j = e[i]; // j是当前邻边的终点节点// 如果通过ver节点到j的距离 比 原来记录的到j的距离更短if (dist[j] > dist[ver] + w[i]){dist[j] = dist[ver] + w[i]; // 更新j的最短距离heap.push({dist[j], j}); // 新的距离和节点入堆（可能重复，后续跳过即可）}}}// 如果n号节点的距离还是无穷大，说明无法到达，返回-1；否则返回最短距离if (dist[n] == 0x3f3f3f3f) return -1;return dist[n];
}int main()
{// 输入节点数n和边数m（scanf比cin快，适配1e6级别的数据量）scanf("%d%d", &n, &m);// 初始化邻接表头指针为-1（所有节点初始无邻边）memset(h, -1, sizeof h);// 循环输入m条边while (m -- ){int a, b, c;scanf("%d%d%d", &a, &b, &c); // 输入边的起点a、终点b、权值cadd(a, b, c); // 添加这条有向边到邻接表}// 调用Dijkstra算法，输出1号到n号节点的最短距离printf("%d\n", dijkstra());return 0;
}