求最短路的边数
给出一个无向图, 求 点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; // 邻接矩阵
bitset<N> vis; // 等同于 bool 数组
int dist; // 距离
int path; // 边的数量
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 = 0;
heap.push({1, 0});
while(!heap.empty()){
auto p = heap.top();
heap.pop();
if(vis) continue;
vis = 1;
for(auto ed : e){
if(dist > dist + ed.w){
dist = dist + ed.w;
heap.push({ed.to, dist});
path = path + 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.push_back({b, c});
e.push_back({a, c});
}
dijkstra();
cout << dist << ' ' << path << endl;
for(int i = 1; i <= n; i++){
cout << path << ' '; // 就是这个边数求不对 , 求解
}
return 0;
}
输入 : 3 3
1 3 2
1 2 1
2 3 1
输出 : 2 3
页:
[1]