这份代码有什么问题
查看原帖
这份代码有什么问题
873417
Istruggle楼主2023/7/18 09:16

找不到问题呀!

#include<bits/stdc++.h>
using namespace std;
int n,m,s;
int head[100005],cnt=0;
int dis[100005],vis[100005]={0};
struct edge
{
	int v,w,next;
}e[500005];
struct node
{
	int u,d;
	bool operator <(const node& rhs) const
	{
		return d>rhs.d;
	}
};
void addedge(int u,int v,int w)
{
	e[cnt++].v=v;
	e[cnt].w=w;
	e[cnt].next=head[u];
	head[u]=cnt;
}
void dij()
{
	for(int i = 1;i<=n;i++) dis[i]=0x3f;
	priority_queue<node> Q;
	Q.push((node){s,0});
	dis[s]=0;
	while(!Q.empty())
	{
		node fr=Q.top(); Q.pop();
		int u=fr.u; int d=fr.d;
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=head[u];i;i=e[i].next)
		{
			int y = e[i].v;
            if(dis[y]>dis[u]+e[i].w )
            {
                dis[y]=dis[u]+e[i].w;
                if(!vis[y])
                {
                    Q.push((node){dis[y], y} );
                }
            }
		}
	}
}
int main()
{
	scanf("%d%d%d",&n,&m,&s); 
	for(int i = 1;i<=m;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		addedge(a,b,c);
	}
	dij();
	for(int i = 1;i<=n;i++)
	cout<<dis[i]<<" ";
	return 0;
}
2023/7/18 09:16
加载中...