P4779的84分求助!!!

P4779 【模板】单源最短路径(标准版)

行动欲望π @ 2022-08-20 10:24:31

#include<bits/stdc++.h>
using namespace std;
#define int long long
int dis[100010],book[100010];
vector <int > v[200010][10];
struct node{
    int p,zhi;
};
bool  operator <(node n1,node n2){
    return n1.zhi >n2.zhi;
}
priority_queue<node> q;
signed main(){
    int n,m,s;
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int u,v1,w;
        cin>>u>>v1>>w;
        v[u][1].push_back(v1);
        v[u][2].push_back(w);
    }
    for(int i=1;i<=n;i++){
        dis[i]=0x7ffffff;
    }
    dis[s]=0;

    /*for(int j=0;j<v[s][1].size();j++){
        int yy=v[s][1][j];
            dis[yy]=min(dis[yy],dis[s]+v[s][2][j]);q.push({yy,dis[yy]});
        }*/q.push({s,0});
    while(q.size()>0){
        node n1=q.top();
        q.pop();
        int hhh=n1.p;
        /*for(int j=1;j<=n;j++){
            if(dis[j]!=0x7ffffff&&book[j]!=1){
            jjj=min(dis[n],jjj);
            if(jjj==dis[n]){
                hhh=n;
            }
            }

        }*/
        if(book[hhh]==1) continue;
        book[hhh]=1;
        for(int j=0;j<v[hhh][1].size();j++){
            int hh=v[hhh][1][j];
            dis[hh]=min(dis[hh],dis[hhh]+v[hhh][2][j]);
            q.push({hh,dis[hh]});
        }
    }   

    for(int i=1;i<=n;i++){
 cout<<dis[i]<<' ';
}
return 0;
}

by 行动欲望π @ 2022-08-20 10:25:46

第5个测试点没过…… _

_


by Fish9块1 @ 2022-08-20 10:32:17

@行动欲望π 单向边。


by 行动欲望π @ 2022-08-20 10:51:00

谢谢,我已经找到错了万分感谢……@Fish9块1


|