迪杰斯特拉求调，P4779标准版已过，弱化版WA#2#9#10

代码如下：

#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){
    return x.quan>y.quan;
}

priority_queue <T> p;

int main(){
    long long MA=99999999999;
//  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]=MA;
    }
    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++){
        if(ans[i]==MA){
            cout <<"2147483647 ";
            continue;
        }
        cout <<ans[i]<<" ";
    }
    return 0;
}