求助一下各位,用了一个基于BFS的Dijkstra,已经AC。现在我希望把找到的最短路径记录在一个数组里应该要怎么操作呢
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100010, M = 1000010;
int head[N], ver[M], edge[M], Next[M], d[N];
bool v[N];
int n, m, tot, s;
priority_queue< pair<int, int> > q; //1距离的相反数 2节点编号 默认大顶堆
void add(int x, int y, int z) { //邻接表
if(x!=y)
{
ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
}
}
void dijkstra() {
//memset(d, 99999, sizeof(d));
for(int i=0;i<N;i++)
{
d[i]=2147483647;
}
memset(v, 0, sizeof(v));
d[s] = 0;
q.push(make_pair(0, s));
while (q.size()) {
int x = q.top().second; q.pop(); //得到堆顶最小距离的点x
if (v[x]) continue;
v[x] = 1;
for (int i = head[x]; i; i = Next[i]) {
int y = ver[i], z = edge[i];
if (d[y] > d[x] + z) { //松弛操作更新距离
d[y] = d[x] + z;
q.push(make_pair(-d[y], y));
}
}
}
}
int main() {
int o;
for(o=0;o<N;o++)
{
head[o]=0;
v[o]=0;
}
for(o=0;o<M;o++)
{
ver[o]=0;
edge[o]=0;
Next[o]=0;
} //初始化
cin >> n >> m >> s; //n: 顶点数 m:连边数 s:起始点
for (int i = 1; i <= m; i++) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
add(x, y, z);
}
dijkstra();
for (int i = 1; i <= n; i++)
cout<<d[i]<<" ";
}
谢谢各位了