52分求助

gyc071116 @ 2024-10-26 10:51:24

#include<bits/stdc++.h>
using namespace std;
struct ee{
    int u;
    int next;
    int val;
}edge[200005];
int h[100005],etot,path[100005];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
void add_edge(int v,int u,int val){
    edge[etot]=(ee){u,h[v],val};
    h[v]=etot++;
}
int main(){
    int n,m,s;
    scanf("%d %d %d",&n,&m,&s);
    for(int i=1;i<=n;i++){
        h[i]=-1;
        path[i]=0x3f3f3f3f;
    }
    for(int i=1;i<=m;i++){
        int c,cc,y;
        scanf("%d %d %d",&c,&cc,&y);
        add_edge(c,cc,y);
    }
    path[s]=0;
    q.push(make_pair(s,0));
    while(!q.empty()){
        int Node=q.top().first,Path=q.top().second;
        q.pop();
        if(Path==path[Node]){
            for(int i=h[Node];i!=-1;i=edge[i].next){
                if(edge[i].val+Path<path[edge[i].u]){
                    path[edge[i].u]=edge[i].val+Path;
                    q.push(make_pair(edge[i].u,path[edge[i].u]));
                }
            }
        }
    }
    for(int i=1;i<=n;i++) printf("%d ",path[i]);
    return 0;
}

by naroto2022 @ 2024-10-26 10:55:30

@gyc071116 优先队列的优先级是 pair 的第一个元素！

你要按 Path 来排序，但是你把 Path 放到了第二个

改过的 AC 代码：

#include<bits/stdc++.h>
using namespace std;
struct ee{
    int u;
    int next;
    int val;
}edge[200005];
int h[100005],etot,path[100005];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
void add_edge(int v,int u,int val){
    edge[etot]=(ee){u,h[v],val};
    h[v]=etot++;
}
int main(){
    int n,m,s;
    scanf("%d %d %d",&n,&m,&s);
    for(int i=1;i<=n;i++){
        h[i]=-1;
        path[i]=0x3f3f3f3f;
    }
    for(int i=1;i<=m;i++){
        int c,cc,y;
        scanf("%d %d %d",&c,&cc,&y);
        add_edge(c,cc,y);
    }
    path[s]=0;
    q.push(make_pair(0,s));
    while(!q.empty()){
        int Node=q.top().second,Path=q.top().first;
        q.pop();
        if(Path==path[Node]){
            for(int i=h[Node];i!=-1;i=edge[i].next){
                if(edge[i].val+Path<path[edge[i].u]){
                    path[edge[i].u]=edge[i].val+Path;
                    q.push(make_pair(path[edge[i].u],edge[i].u));
                }
            }
        }
    }
    for(int i=1;i<=n;i++) printf("%d ",path[i]);
    return 0;
}

by gyc071116 @ 2024-10-26 10:59:54

@naroto2022 非常感谢