WA求助,悬关

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

ylm0x7D9 @ 2023-07-18 16:45:42

#include<bits/stdc++.h>
using namespace std;
struct Side{
    int w,nxt,to;
}sds[200001];
int sdh[200001];
long long pl[100001];
bool f[100001]; 
struct Point{
    int l,si;
    bool operator<(const Point &x) const{
        return l<x.l;
    } 
};
priority_queue<Point> que;
int main(){
    int n,m,s;
    cin>>n>>m>>s;
    int frm,to,w;
    for(int i=1;i<=m;i++){
        cin>>frm>>to>>w;
        sds[i].to=to;
        sds[i].w=w;
        sds[i].nxt=sdh[frm];
        sdh[frm]=i;
    }
    Point p;
    p.l=0,p.si=s;
    que.push(p);
    int INF=(1<<31)-1;
    for(int i=1;i<=n;i++) pl[i]=INF;
    pl[s]=0;
    while(que.size()){
        p=que.top();
        que.pop();
        int x=p.si;
        if(f[x]) continue;
        f[x]=true;
        for(int j=sdh[x];j!=0;j=sds[j].nxt){
            int y=sds[j].to;
            if(pl[y]>pl[x]+sds[j].w){
                pl[y]=pl[x]+sds[j].w;
                p.si=y;
                p.l=pl[y];
                que.push(p);
            }
        }
    }
    for(int i=1;i<=n;i++) cout<<pl[i]<<" ";
    return 0;
}

只对了第五个点


by chenjliang @ 2023-07-18 20:26:30

第12行应该是

return l>x.l;

不是l<x.l


by ylm0x7D9 @ 2023-07-19 14:24:51

@chenjliang 原来是这,谢谢谢谢


|