各位神犇， 帮帮蒟蒻吧， 样例#2，#3，#6过不了。【QWQ】

Wangfeiyang @ 2023-08-25 13:28:52

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
typedef pair<int, int> p;

struct node { 
    int id, w;
    friend bool operator < (node a, node b){
        return a.w > b.w;
    }
};

int n, m, s;
vector<p> v[N];
int dis[N], vis[N];

void dijkstra(int s){
    dis[s] = 0;
    priority_queue<node> q;
    q.push(node{s, 0});

    while( !q.empty() ){
        node tmp = q.top(); q.pop();
        if(vis[tmp.id]) continue;
        vis[tmp.id] = true;

        for(int i = 0; i < v[tmp.id].size(); i ++){
            int j = v[tmp.id][i].first;
            int k = v[tmp.id][i].second;
            if(tmp.w + k < dis[j] && !vis[j]){
                dis[j] = tmp.w + k;
                q.push(node{j, dis[j]});
            }
        }
    }
}

int main() {
    cin >> n >> m >> s;
    for(int i = 1; i <= m; i ++){
        int x, y, z;
        cin >> x >> y >> z;
        v[x].push_back(make_pair(y, z));
    }

    memset(dis, 0x3f, sizeof dis);
    memset(vis, 0, sizeof vis);
    dijkstra(s);

    int a = INT_MAX;
    for(int i = 1; i <= n; i ++){
        if(dis[i] == 0x3f) cout << a << " ";
        else cout << dis[i] << " ";
    }
    return 0;
}

by FiraCode @ 2023-08-25 13:40:00

@Wangfeiyang 《dis[i] == 0x3f》

by FiraCode @ 2023-08-25 13:40:22

应该是 dis[i] == 0x3f3f3f3f

by Wangfeiyang @ 2023-08-25 13:53:10

@FiraCode 大神， 这样改了之后还是那样啊。【泪奔】

by FiraCode @ 2023-08-25 13:55:44

@Wangfeiyang

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
typedef pair<int, int> p;

struct node { 
    int id, w;
    friend bool operator < (node a, node b){
        return a.w > b.w;
    }
};

int n, m, s;
vector<p> v[N];
int dis[N], vis[N];

void dijkstra(int s){
    dis[s] = 0;
    priority_queue<node> q;
    q.push(node{s, 0});

    while( !q.empty() ){
        node tmp = q.top(); q.pop();
        if(vis[tmp.id]) continue;
        vis[tmp.id] = true;

        for(int i = 0; i < v[tmp.id].size(); i ++){
            int j = v[tmp.id][i].first;
            int k = v[tmp.id][i].second;
            if(tmp.w + k < dis[j] && !vis[j]){
                dis[j] = tmp.w + k;
                q.push(node{j, dis[j]});
            }
        }
    }
}

int main() {
    cin >> n >> m >> s;
    for(int i = 1; i <= m; i ++){
        int x, y, z;
        cin >> x >> y >> z;
        v[x].push_back(make_pair(y, z));
    }

    memset(dis, 0x3f, sizeof dis);
    memset(vis, 0, sizeof vis);
    dijkstra(s);

    int a = INT_MAX;
    for(int i = 1; i <= n; i ++){
        if(dis[i] == 0x3f3f3f3f) cout << a << " "; //这里
        else cout << dis[i] << " ";
    }
    return 0;
}

by FiraCode @ 2023-08-25 13:55:56

@Wangfeiyang 我这里过了啊

by Wangfeiyang @ 2023-08-25 13:59:35

@FiraCode 大神，我的问题， 我只改了初始化，输出时的判断没改。【汗颜】， 谢谢大神。【抱拳】