求最短路的边数

柿子饼同学

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

#include <bits/stdc++.h>
using namespace std;

struct edge{ // 边
        int to, w;
};
struct node{ // 点
        int code, dist;
};
struct cmp{
        inline bool operator()(const node & a, const node & b){
                return a.dist > b.dist;
        }
};
const int N = 20005;
priority_queue<node, vector<node>, cmp> heap; // 堆优化
vector<edge> e[N]; // 邻接矩阵
bitset<N> vis; // 等同于 bool 数组
int dist[N]; // 距离
int path[N]; // 边的数量
int n, m, a, b, c; // n个点, m条边, 由 a 到 b 的权值为 c 的边

void dijkstra(){
        vis.reset();
        memset(dist, 0x3f, sizeof(dist));
        memset(path, 0, sizeof(path)); // 初始化
        dist[1] = 0;
        heap.push({1, 0});
        while(!heap.empty()){
                auto p = heap.top();
                heap.pop();
                if(vis[p.code]) continue;
                vis[p.code] = 1;
                for(auto ed : e[p.code]){
                        if(dist[ed.to] > dist[p.code] + ed.w){
                                dist[ed.to] = dist[p.code] + ed.w;
                                heap.push({ed.to, dist[ed.to]});
                                path[ed.to] = path[p.code] + 1; // 这里加最短路的边 , 不知道为什么不对
                        }
                }
        }
}

int main(){
        ios::sync_with_stdio(0);
        cin.tie(0); cout.tie(0);
        
        cin >> n >> m;
        for(int i = 0; i < m; i++){
                cin >> a >> b >> c;
                e[a].push_back({b, c});
                e[b].push_back({a, c});
        }

        dijkstra();

        cout << dist[n] << ' ' << path[n] << endl;
        for(int i = 1; i <= n; i++){
                cout << path[i] << ' '; // 就是这个边数求不对 , 求解
        }
        
        return 0;
}

输入 :

3 3 
1 3 2
1 2 1
2 3 1

输出 :

2 3