社区讨论
为什么更改了add函数的细节就会有问题
P4779【模板】单源最短路径(标准版)参与者 3已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @m1tc7xwm
- 此快照首次捕获于
- 2024/10/03 21:33 去年
- 此快照最后确认于
- 2025/11/04 18:10 4 个月前
AC 100pts 代码
CPP#include <bits/stdc++.h>
#define maxn 100003
using namespace std;
struct Edge {
int v, w, next;
}edge[200003];
struct Data {
int dis, pos;
bool operator < (const Data &x) const {
return x.dis < dis;
}
};
int n, m, s, head[maxn], vis[maxn], dis[maxn];
int cnt;
priority_queue<Data> q;
void add(int u, int v, int w) {
cnt++;
edge[cnt].v = v;
edge[cnt].w = w;
edge[cnt].next = head[u];
head[u] = cnt;
}
void dijkstra() {
memset(dis, 0x3f, sizeof(dis));
dis[s] = 0;
q.push((Data){0, s});
while (q.size()) {
Data f = q.top();
q.pop();
int pos = f.pos;
if (vis[pos]) {
continue;
}
vis[pos] = 1;
for (int i = head[pos]; i; i = edge[i].next) {
int v = edge[i].v, w = edge[i].w;
if (dis[v] > dis[pos] + w) {
dis[v] = dis[pos] + w;
if (vis[v] == 0) {
q.push((Data){dis[v], v});
}
}
}
}
}
int main() {
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
cin >> n >> m >> s;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
add(u, v, w);
}
dijkstra();
for (int i = 1; i <= n; i++) {
cout << dis[i] << " ";
}
return 0;
}
其中,我把 add 函数从上述的
CPPvoid add(int u, int v, int w) {
cnt++;
edge[cnt].v = v;
edge[cnt].w = w;
edge[cnt].next = head[u];
head[u] = cnt;
}
改为了:
CPPvoid add(int u, int v, int w) {
edge[cnt++].v = v;
edge[cnt].w = w;
edge[cnt].next = head[u];
head[u] = cnt;
}
就会出错啊?
更改后的样例输出变为了:
CPP0 1061109567 2 5
回复
共 3 条回复,欢迎继续交流。
正在加载回复...