52分 求调 悬关

wzhmyt @ 2024-10-15 21:26:40

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
struct edge {
    int v, w;
};
struct node {
    int dis, u;
    bool operator > (const node& a) const {
        return dis > a.dis;
    }
};
vector<edge> e[maxn];
int dis[maxn], vis[maxn];
priority_queue<node, vector<node>, greater<node> > q;
int n, m, s;
void dijkstra(int n, int s) {
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    q.push({0, s});
    while(!q.empty()) {
        int u = q.top().u;
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (auto ed : e[u]) {
            int v = ed.v, w = ed.w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                q.push({dis[v], v});
            }
        }
    }
}
int main() {
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }
    memset(vis, 0, sizeof(vis));
    dijkstra(n, s);
    for (int i = 1; i <= n; i++) cout << dis[i] << " ";
    return 0;
}

by shixuanzhe_ha @ 2024-10-15 21:28:54

@wzhmyt 重载运算符错了

by wzhmyt @ 2024-10-15 21:29:16

应该怎么写

by shixuanzhe_ha @ 2024-10-15 21:34:01

@wzhmyt 等一下

by shixuanzhe_ha @ 2024-10-15 21:37:57

@wzhmyt A 了

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 5e5 + 5;
struct edge {
    int v, w;
};
struct node {
    int dis, u;
    bool operator < (const node &a) const {
        return dis > a.dis;
    }
};
vector<edge> e[maxn];
int dis[maxn], vis[maxn];
priority_queue<node> q;
int n, m, s;
void dijkstra(int s) {
    for(int i = 1; i <= n; i++)
        dis[i] = 2147483647;
    dis[s] = 0;
    q.push({0, s});
    while(!q.empty()) {
        int u = q.top().u;
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (auto ed : e[u]) {
            int v = ed.v, w = ed.w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                q.push({dis[v], v});
            }
        }
    }
}
signed main() {
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back({v, w});
    }
    memset(vis, 0, sizeof(vis));
    dijkstra(s);
    for (int i = 1; i <= n; i++) cout << dis[i] << " ";
    return 0;
}

by shixuanzhe_ha @ 2024-10-15 21:40:25

@wzhmyt

1. 你的重载运算符错了，默认大根堆。 STL 里大根堆用的是小于号，小根堆用的是大于号。

2. 单向边

3. 无解要输出 2^{31} - 1。

by wzhmyt @ 2024-10-15 21:41:09

ok 谢谢大佬 已关

by Huangjh1 @ 2024-10-20 19:11:59

重载的运算符应该是小于号，因为你要做的操作是把小根堆变成大根堆