学dijkstra的预备知识dijkstra的数学逻辑可以看我dijkstra算法那一篇dijkstra算法-CSDN博客优先队列邻接矩阵邻接表邻接矩阵邻接表链式前向星-CSDN博客没问题咱们不背模板直接从 Dijkstra 的**“三个核心动作”**出发像搭积木一样把代码推导出来。第一步建立“记忆”——我需要存什么既然逻辑是“从起点像波浪一样扩散”程序就必须记录每个点的状态。距离记忆得有个地方记下“目前到每个城市最少花多少钱”。代码推导int dist[2010];。刚开始大家都是陌生人设为无穷大 INF。路线计数得有个地方记下“到这个城市的最短路有几条”。代码推导int cnt[2010];。确定名单得知道哪些城市的“绿灯”已经亮了最短路已确定不再重复处理。代码推导可以用 bool visited[2010];。也可以在dijkstra中用if(d dist[u])continue;处理第二步选择工具——怎么选出“下一个”Dijkstra 逻辑中最重要的动作是在所有还没确定最短路的点中选一个距离最近的。暴力想每次遍历 dist 数组找最小值。时间复杂度 $O(N^2)$慢。聪明想我们需要一个能“自动排序”的容器每次直接把最小的弹给我。代码工具priority_queue优先队列/堆。注意C 的优先队列默认是大顶堆先弹最大的我们要找最短距离所以要加 greater 变成小顶堆priority_queuepairint, int, vectorpairint, int, greaterpairint, int pq;(这里存 pair 是为了把“距离”和“城市编号”绑在一起)第三步核心循环——三个动作循环往复这就是 while(!pq.empty()) 里的内容。想象你手中拿着这张地图1. 弹出当前最优先的目标Cint d pq.top().first; // 当前记录的距离int u pq.top().second; // 城市的编号pq.pop();2. 检查是否是“二手信息”因为同一个点可能被多次丢进堆里如果弹出来的距离 d 比我们记录的 dist[u] 还要大说明这已经是一条“旧路”了直接扔掉Cif (d dist[u]) continue;3. 考察邻居松弛操作这是逻辑升华的地方。站在城市 u看它连着的邻居 v边权为 w。推导逻辑如果 我现在的开销 走过去的开销 邻居原来的开销代码实现Cfor (auto edge : adj[u]) {int v edge.first;int w edge.second;if (dist[u] w dist[v]) {dist[v] dist[u] w; // 更新距离cnt[v] cnt[u]; // 路径条数继承因为发现新大陆以前的走法都太慢了pq.push({dist[v], v}); // 把这个更优的点丢进堆里去影响别人} else if (dist[u] w dist[v]) {cnt[v] cnt[u]; // 路径条数累加发现了一样短的走法}}第四步输入去重——解决题目“点序列”要求你已经知道了这道题的特殊性点序列不同才算。推导如果在输入时发现 $1 \to 2$ 有两条路开销分别是 2 和 3。逻辑开销 3 的路永远不会成为最短路如果两条路开销都是 2走哪条点序列都是 [1, 2]按题目要求只能算 1 条。代码实现在存入邻接表adj之前用一个简单的 min_w[u][v] 矩阵过滤一下Cif (c min_w[u][v])min_w[u][v] c; // 只留最小的教练的最后点拨你可以把 Dijkstra 代码想象成一个**“消息扩散系统”**起点发了个朋友圈“我到 1 号城花费 0走法 1 种”。堆负责按花费排序让“最省钱的消息”先发布。邻居们听到消息后如果发现比自己原来的开销小就赶紧更新自己的朋友圈并转发出去。你看按照这个“存什么 - 怎么选 - 怎么更新”的步骤代码是不是就不再是一堆死记硬背的字符而是一个有逻辑的生命体了 要不要试着根据这个思路不看模板自己手写一遍 while 循环写不出来的地方我再帮你抠细节。// dijkstra #include iostream #include cstring #include vector #include queue using namespace std; #define int long long #define endl \n int n 0,m 0; int min_w[2010][2010] {0}; // 邻接矩阵用于去重 vectorpairint, int adj[2010]; // 邻接表用于 Dijkstra int dist[2010] {0}; // 目前到每个城市最少花多少钱 int cnt[2010] {0}; // 到这个城市的最短路有几条 //bool visited[2010] {0}; // 哪些城市的“绿灯”已经亮了最短路已确定不再重复处理 priority_queue pairint,int , vectorpairint,int , greaterpairint,int pq; signed main(){ // 关闭同步流 ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); // 输入加处理重边 cin n m; for(int u 1 ; u n ; u){ dist[u] 1LL 60; for(int v 1 ; v n ; v){ min_w[u][v] 1LL 60; } } memset(min_w,0x3f,sizeof(min_w)); // #include cstring for(int i 1 ; i m ; i){ int u,v,c; cin u v c; if(c min_w[u][v])min_w[u][v] c; } for(int u 1 ; u n ; u){ for(int v 1 ; v n ; v){ adj[u].push_back({v,min_w[u][v]}); } } // 2. Dijkstra 标准初始化 for(int i 1; i n; i) dist[i] 1LL 60; dist[1] 0; cnt[1] 1; pq.push({0, 1}); // 3. 开始dijkstra while(!pq.empty()){ int d pq.top().first; // 当前距离 int u pq.top().second; // 当前城市 pq.pop(); // 弹出堆顶 // 核心如果这个点已经有更短路径了就跳过这个“旧信息”那visited可以不要了 if(d dist[u])continue; // 遍历 u 的所有邻居 for(auto edge : adj[u]){ int v edge.first; int w edge.second; // 如果路径无效比如刚初始化时是 INF跳过 if (w 1LL 60) continue; if(dist[u] w dist[v]){ dist[v] dist[u] w; // 更新更短距离 cnt[v] cnt[u]; // 继承路径数 pq.push({dist[v],v}); // 把新距离推入堆 } else if(dist[u] w dist[v])cnt[v] cnt[u]; } } if(dist[n] 1LL 60)cout No answer endl; else cout dist[n] cnt[n] endl; return 0; }