求调，我老师也看不出来什么问题

QWQ_guangmiao @ 2024-05-18 21:40:03

#include <bits/stdc++.h>
using namespace std;
long long n,m,s,id[500000],ans[500000];

struct T{
    long long you,quan;
};

vector <T> q[500005];

bool operator<(T x,T y){
    x.quan<y.quan;
}

priority_queue <T> p;

int main(){
//  freopen("P4779_1.in","r",stdin);
//  freopen("1.txt","w",stdout);
    cin >>n>>m>>s;
    for(long long i=1;i<=n;i++){
        ans[i]=0x3f3f3f3f;
    }

    for(long long i=1;i<=m;i++){
        long long u,v,w;
        cin >>u>>v>>w;
        q[u].push_back((T){v,w});
        id[i]=0;
    }
    p.push((T){s,0});
    ans[s]=0;
//  id[s]=1;
//  long long pd=1;
    while(p.empty()==0){
        T d=p.top();
        long long dd=d.you;
        long long ddd=d.quan;
        p.pop();
        if(id[dd]==1){
//          pd++;
            continue;
        }
        id[dd]=1;
        for(long long i=0;i<q[dd].size();i++){
            long long q1=q[dd][i].you;
            long long q2=q[dd][i].quan;
            if(ans[q1]>ans[dd]+q2){
                ans[q1]=ans[dd]+q2;
//              if(id[q1]!=1){
                    p.push((T){q1,ans[q1]});
//              }
            }
        }
    }
    ans[s]=0;
    for(long long i=1;i<=n;i++){
        cout <<ans[i]<<" ";
    }
    return 0;
}

by xudongyi1 @ 2024-05-18 22:03:03

@QWQ_guangmiao 如下

#include <bits/stdc++.h>
using namespace std;
long long n,m,s,id[1000000],ans[1000000];

struct T{
    long long you,quan;
    bool operator < (const T &a) const
    {
        return quan > a.quan;
    }
    ////主要在这里
};

vector <T> q[1000005];

priority_queue <T> p;

int main(){
//  freopen("P4779_1.in","r",stdin);
//  freopen("1.txt","w",stdout);
    cin >>n>>m>>s;
    for(long long i=1;i<=n;i++){
        id[i] = 0;
        ans[i]=1e18;
    }

    for(long long i=1;i<=m;i++){
        long long u,v,w;
        cin >>u>>v>>w;
        q[u].push_back((T){v,w});
    }
    p.push((T){s,0});
    ans[s]=0;
//  id[s]=1;
//  long long pd=1;
    while(p.empty()==0){
        T d=p.top();
        long long dd=d.you;
        long long ddd=d.quan;
        p.pop();
        if(id[dd]==1){
//          pd++;
            continue;
        }
        id[dd]=1;
        for(long long i=0;i<q[dd].size();i++){
            long long q1=q[dd][i].you;
            long long q2=q[dd][i].quan;
            if(!id[q1] && ans[q1]>ans[dd]+q2){
                ans[q1]=ans[dd]+q2;
                if(id[q1]!=1){
                    p.push((T){q1,ans[q1]});
                }
            }
        }
    }
    for(long long i=1;i<=n;i++){
        cout <<ans[i]<<" ";
    }
    return 0;
}

by QWQ_guangmiao @ 2024-05-20 13:56:57

@xudongyi1 谢谢dalao ORZ