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 原来是这,谢谢谢谢