52分求调
查看原帖
52分求调
1476677
llll123321楼主2024/10/8 17:28

过了三个点,没过三个点. 求大佬调一调程序

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1,M=2e5+1;
struct edge 
{
	int u,v,n,w;
}e[M];
int fl[N],head[N];
int n,m,dis[N],s,cnt=0;
struct point 
{
	int p,dis;
	bool operator < (point x)const{return dis>x.dis;}
};
priority_queue<point> q;
inline int read() 
{
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
void dij()
{
	dis[s]=0;
	q.push((point){s,dis[s]});
	while(!q.empty())
	{
		int top=q.top().p;
		q.pop();
		for(int i=head[top];i;i=e[i].n)
		{
			if(dis[e[i].v]>dis[top]+e[i].w)
			{
				dis[e[i].v]=dis[top]+e[i].w;
				if(fl[e[i].v]==0) {fl[e[i].v]=1;q.push((point){e[i].v,dis[e[i].v]});}
			}
		}
	}
}
int main()
{
	memset(fl,0,sizeof(fl)); memset(head,0,sizeof(head));  memset(dis,0x6f,sizeof(dis));
	n=read();m=read();s=read();
	cerr<<n<<m<<s;
	for(int i=1;i<=m;i++)
	{
		int u=read(),v=read(),w=read();
		e[++cnt]=(edge){u,v,head[u],w};
		head[u]=cnt;
	}
	fl[s]=1;
	dij();
	for(int i=1;i<=n;i++)cout<<dis[i]  <<" ";
	return 0;
}

2024/10/8 17:28
加载中...