chasing_dream @ 2022-07-04 21:45:20
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
register int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
return x*f;
}
const int maxn=1e5+10;
const int maxm=2e5+10;
const int inf=0x7f;
struct edge
{
int dis,next,to;
}a[maxm];
struct node
{
int d,p;//d是距离,u是当前节点
bool operator <( const node &x )const
{
return x.d<d;
}
};
int dis[maxn],head[maxn],n,m,s,cnt;
bool vis[maxn];
priority_queue<node>q;
void addedge(int u,int v,int w)
{
cnt++;
a[cnt].dis=w;
a[cnt].to=v;
a[cnt].next=head[u];
head[u]=cnt;
}
int main()
{
n=read(),m=read(),s=read();
for(int i=1;i<=n;i++) dis[i]=inf;
for(int i=1;i<=m;i++)
{
int u=read(),v=read(),w=read();
addedge(u,v,w);
}
dis[s]=0;
q.push((node){0,s});
while(!q.empty())
{
node tmp=q.top();
q.pop();
int u=tmp.p;
if(vis[u]) continue;
vis[u]=1;
for(int i=head[i];i;i=a[i].next)
{
if(dis[a[i].to]>dis[u]+a[i].dis)
{
dis[a[i].to]=dis[u]+a[i].dis;
if(!vis[a[i].to])
q.push((node){dis[a[i].to],a[i].to});
}
}
}
for(int i=1;i<=n;i++) cout<<dis[i]<<' ';
return 0;
}
by qwasd @ 2022-07-04 21:49:48
@chasing_dream priority_queue
默认大根堆,所以 return x.d<d;
应该改成 return x.d>d;
。
by chasing_dream @ 2022-07-04 21:51:32
@qwasd 还错
by Anonymely @ 2022-07-04 21:54:45
@chasing_dream
i=a[i].i
错了吧
by chasing_dream @ 2022-07-04 21:56:25
@trisomy 在哪里
by Anonymely @ 2022-07-04 22:02:30
@chasing_dream
for(int i=head[i];i;i=a[i].next)
by chasing_dream @ 2022-07-04 22:11:35
@trisomy 改成了i=head[u] 样例过了,但是还是错
by a16_ @ 2022-07-04 22:31:11
@chasing_dream inf=1e9
by a16_ @ 2022-07-04 22:32:42
还有,重载运算符不用改
by chasing_dream @ 2022-07-05 10:53:17
@上清沦谪 谢谢!