带权最短路 · 298 · 公开题解

思路

非负边权使用 Dijkstra，并用优先队列维护当前最小距离点。

复杂度

$O((n+m)log n)$ 时间，$O(n+m)$ 空间。

易错点

• 认真处理最小规模、重复值、不可达或全负数等边界。
• 需要累加的题目优先使用 64 位整数。
• 不要根据样例特判；隐藏数据包含随机、边界与退化结构。

C++17 参考实现

#include <bits/stdc++.h>
using namespace std;
int main(){int n,m,u,v,w;cin>>n>>m;vector<vector<pair<int,int>>>g(n+1);while(m--){cin>>u>>v>>w;g[u].push_back({v,w});}const long long I=4e18;vector<long long>d(n+1,I);priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>q;d[1]=0;q.push({0,1});while(!q.empty()){auto [du,x]=q.top();q.pop();if(du!=d[x])continue;for(auto [y,z]:g[x])if(d[y]>du+z)d[y]=du+z,q.push({d[y],y});}cout<<(d[n]==I?-1:d[n])<<'\n';}

来源与授权

• 题目与数据： 智链细米 IT 社区原创训练变体（dijkstra-0096）。
• 知识路线参考： AlgoNote @ 2aa4fd0a2214；代码随想录 @ b43def349578。
• 引用说明： 代码随想录作者为程序员 Carl；本题没有复制 LeetCode 或第三方竞赛题面、样例、题解与测试数据。
• 授权记录： organizer-confirmed-2026-08-07。
• 主办方： 智链细米 IT 社区；设备支持： EaglesLab。