求最短路的边数

柿子饼同学

给出一个无向图, 求 点1 -> 点n 的最短路, 并求出最短路上有几条边
最短路算法我可以了, 但是如何统计最短路上边数错了, 求一个方法, 我代码在下面:

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. struct edge{ // 边
   
5.         int to, w;
   
6. };
   
7. struct node{ // 点
   
8.         int code, dist;
   
9. };
   
10. struct cmp{
    
11.         inline bool operator()(const node & a, const node & b){
    
12.                 return a.dist > b.dist;
    
13.         }
    
14. };
    
15. const int N = 20005;
    
16. priority_queue<node, vector<node>, cmp> heap; // 堆优化
    
17. vector<edge> e[N]; // 邻接矩阵
    
18. bitset<N> vis; // 等同于 bool 数组
    
19. int dist[N]; // 距离
    
20. int path[N]; // 边的数量
    
21. int n, m, a, b, c; // n个点, m条边, 由 a 到 b 的权值为 c 的边
    
22. 
    
23. void dijkstra(){
    
24.         vis.reset();
    
25.         memset(dist, 0x3f, sizeof(dist));
    
26.         memset(path, 0, sizeof(path)); // 初始化
    
27.         dist[1] = 0;
    
28.         heap.push({1, 0});
    
29.         while(!heap.empty()){
    
30.                 auto p = heap.top();
    
31.                 heap.pop();
    
32.                 if(vis[p.code]) continue;
    
33.                 vis[p.code] = 1;
    
34.                 for(auto ed : e[p.code]){
    
35.                         if(dist[ed.to] > dist[p.code] + ed.w){
    
36.                                 dist[ed.to] = dist[p.code] + ed.w;
    
37.                                 heap.push({ed.to, dist[ed.to]});
    
38.                                 path[ed.to] = path[p.code] + 1; // 这里加最短路的边 , 不知道为什么不对
    
39.                         }
    
40.                 }
    
41.         }
    
42. }
    
43. 
    
44. int main(){
    
45.         ios::sync_with_stdio(0);
    
46.         cin.tie(0); cout.tie(0);
    
47.        
    
48.         cin >> n >> m;
    
49.         for(int i = 0; i < m; i++){
    
50.                 cin >> a >> b >> c;
    
51.                 e[a].push_back({b, c});
    
52.                 e[b].push_back({a, c});
    
53.         }
    
54. 
    
55.         dijkstra();
    
56. 
    
57.         cout << dist[n] << ' ' << path[n] << endl;
    
58.         for(int i = 1; i <= n; i++){
    
59.                 cout << path[i] << ' '; // 就是这个边数求不对 , 求解
    
60.         }
    
61.        
    
62.         return 0;
    
63. }
    

复制代码

输入 :

1. 3 3
   
2. 1 3 2
   
3. 1 2 1
   
4. 2 3 1

复制代码

输出 :

1. 2 3

复制代码