【题目来源】
【题目描述】
Mar 星球上共有 n 个城市（编号为 1~n），城市之间为了方便交通修建了 m 条单向高速公路。
有些公路是为了交通方便连接了 2 个不同的城市，有些公路是为了观光方便，从一个城市出发最后还会回到该城市。两个城市之间、以及从本市出发回本市的道路都可能有多条。
作为交通部新来的程序员，你接到了一个第一个任务：已知所有道路起止点以及走该条路需要花的过路费，计算出从 1 号城市到 n 号城市的最低花费？
【输入格式】
第 1 行有 2 个整数 n 和 m（1≤n, m≤10^5）
接下来 m 行，每行有 3 个整数 u、v、p，表示从有一条道路从 u 市连到 v 市，走该条路需要花费 p 元。（1≤u, v≤n，1≤p≤10^4)。
【输出格式】
输出一个整数，代表从 1 号城市到 n 号城市的最少交通费。如果根据给定的数据发现，从 1 号城市无法到达 n 号城市，请输出 -1。
【输入样例】
3 4
1 2 1
1 3 3
2 3 1
1 1 2
【输出样例】
2
【数据范围】
1≤n, m≤10^5，1≤u, v≤n，1≤p≤10^4
【算法分析】
● Dijkstra 算法
Dijkstra 算法是一种用于解决有权图中单源最短路径问题的经典算法，由荷兰计算机科学家 Edsger W. Dijkstra 于 1956 年提出。以下是该算法的核心要点：
（1）适用范围：适用于带非负权重的有向图或无向图，无法处理含负权边的图。
（2）核心思想：采用贪心策略，逐步扩展离源点最近的未访问节点，更新邻接节点的最短距离。
● Dijkstra 算法的堆优化
（1）朴素 Dijkstra 算法每次需遍历所有节点寻找距离起点最近的未访问节点，造成大量冗余计算，致朴素 Dijkstra 算法的总时间复杂度为 O(n²)。特别的，在节点数较多时（如 n=10⁵）性能急剧下降。
（2）而堆优化 Dijkstra 算法通过优先队列（小根堆）将查找最小距离节点的操作从 O(n) 优化至 O(1)，可使堆优化 Dijkstra 算法的总时间复杂度优化为 O(mlogn)（m为边数）。
（3）堆优化的本质是通过小根堆动态维护最小距离节点和避免全局扫描，将算法效率从 O(n²) 优化至 O(mlogn)，尤其适用于稀疏图或大规模节点场景。
● 链式前向星：
“链式前向星”就是“多单链表”，每条单链表基于“头插法”并用 e[]、ne[]、h[] 、val[] 等数组进行模拟创建。其中：
e[idx]：存储序号为 idx 的边的终点值
ne[idx]：存储序号为 idx 的边指向的边的序号（模拟链表指针）
h[a]：存储头结点 a 指向的边的序号
val[idx]：存储序号为 idx 的边的权值（可选）
● 本题 Dijkstra 算法的两种朴素实现
基于链式前向星的实现，详见：
基于邻接矩阵的实现，详见：
【算法代码】
#include <bits/stdc++.h>
using namespace std;typedef pair<int,int> PII; //<dis,idx>
const int inf=0x3f3f3f3f;
const int N=2e5+5;
int h[N],e[N<<1],ne[N<<1],val[N<<1],idx;
int st[N],dis[N];
int n,m;void add(int a,int b,int w) {val[idx]=w,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}int dijkstra() {priority_queue<PII,vector<PII>,greater<PII>> q;memset(dis,inf,sizeof dis);dis[1]=0;q.push({0,1}); //<dis,idx>while(!q.empty()) {auto t=q.top();q.pop();int u=t.second; //idxif(st[u]) continue;st[u]=true;for(int i=h[u]; i!=-1; i=ne[i]) {int j=e[i];if(dis[j]>dis[u]+val[i]) {dis[j]=dis[u]+val[i];q.push({dis[j],j});}}}if(dis[n]==inf) return -1;return dis[n];
}int main() {memset(h,-1,sizeof(h));cin>>n>>m;while(m--) {int a,b,c;cin>>a>>b>>c;add(a,b,c);}cout<<dijkstra()<<endl;return 0;
}/*
in:
3 3
1 2 2
2 3 1
1 3 4out:
3
*/
【参考文献】