样例没过求条

Cute_Furina @ 2024-09-17 13:25:17

#include<bits/stdc++.h>
using namespace std;
struct edge {
    int to, dis, next;
}e[100010];
struct node {
    int dis, pos;
    bool operator <(const node &x)const {
        return x.dis < dis;
    }
};
priority_queue<node> q;
int head[100010], dis[100010], vis[100010];
int cnt, n, m, s;
void dijkstra() {
    dis[s] = 0;
    q.push((node){0, s});
    while(q.empty() == true) {
        node tmp = q.top();
        q.pop();
        int x = tmp.pos, d = tmp.dis;
        if(vis[x]) continue;
        vis[x] = 1;
        for(int i = head[x]; i != 0; i = e[i].next) {
            if(dis[e[i].to] > dis[x] + e[i].dis) {
                dis[e[i].to] = dis[x] + e[i].dis;
                if(vis[e[i].to] == 0) {
                    q.push((node){dis[e[i].to], e[i].to});
                }
            }
        }
    }
}
int main() {
    cin >> n >> m >> s;
    for(int i = 1;i <= n;i ++) {
        dis[i] = 0x7fffffff;
    }
    for(int i = 1;i <= m;i ++) {
        int u, v, d;
        cin >> u >> v >> d;
        cnt ++;
        e[cnt].dis = d;
        e[cnt].to = v;
        e[cnt].next = head[u];
        head[u] = cnt;
    }
    dijkstra();
    for(int i = 1;i <= n;i ++) {
        cout << dis[i] << " ";
    }
    return 0;
}

by JOKER_chu @ 2024-09-17 13:46:43

总结

@M1saka16I72 他的比较函数里的 dis 是反着的，这里没写错

@difficultlong 就只有“优先队列的条件判断错误”是真实的，其他的都是错误的

@zhangbo1000 同上：他的比较函数里的 dis 是反着的，这里没写错

@Luowj 问题就是链式前向星数组开小了并且优先队列的条件判断错误

AC 代码

#include<bits/stdc++.h>
using namespace std;
struct edge {
    int to, dis, next;
}e[200010];
struct node {
    int dis, pos;
    bool operator <(const node &x)const {
        return x.dis < dis;
    }
};
priority_queue<node> q;
int head[200010], dis[100010], vis[100010];
int cnt, n, m, s;
void dijkstra() {
    dis[s] = 0;
    q.push((node){0, s});
    while(q.empty() == false) {
        node tmp = q.top();
        q.pop();
        int x = tmp.pos, d = tmp.dis;
        if(vis[x]) continue;
        vis[x] = 1;
        for(int i = head[x]; i != 0; i = e[i].next) {
            if(dis[e[i].to] > dis[x] + e[i].dis) {
                dis[e[i].to] = dis[x] + e[i].dis;
                if(vis[e[i].to] == 0) {
                    q.push((node){dis[e[i].to], e[i].to});
                }
            }
        }
    }
}
int main() {
    cin >> n >> m >> s;
    for(int i = 1;i <= n;i ++) {
        dis[i] = 0x7fffffff;
    }
    for(int i = 1;i <= m;i ++) {
        int u, v, d;
        cin >> u >> v >> d;
        cnt ++;
        e[cnt].dis = d;
        e[cnt].to = v;
        e[cnt].next = head[u];
        head[u] = cnt;
    }
    dijkstra();
    for(int i = 1;i <= n;i ++) {
        cout << dis[i] << " ";
    }
    return 0;
}

by Cute_Furina @ 2024-09-17 13:48:12

@JOKER_chu thx，已关

by M1saka16I72 @ 2024-09-17 13:49:31

楼上说的对。