p3371求助
  • 板块灌水区
  • 楼主Ginka_
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/12/27 20:22
  • 上次更新2023/12/27 23:15:01
查看原帖
p3371求助
753837
Ginka_楼主2023/12/27 20:22

为什么过不了w(゚Д゚)w

求dalao解答

#include<bits/stdc++.h>
#define N 200010
#define ll long long
#define inf 2147483647
using namespace std;
int n,m,s,dis[N];
int head[N],nxt[N*2],to[N],val[N*2],cnt;
bool vis[N];
struct node
{
    int w,v;
    inline bool operator <(const node &x)const
    {
    	return w>x.w;
    }
};
priority_queue<node>q;
inline int read()
{
    int x=0,k=1; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();}
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*k;
}
void dijkstra()
{
//	for(int j=1;j<=n;j++)
//	{
//		dis[j]=inf;
//	}
	dis[s]=0;
	q.push((node){0,s});
	while(!q.empty())
	{
		int u=q.top().v;
		q.pop();
		if(vis[u]) continue;
		vis[u]=true;
		for(int i=head[u];i;i=nxt[i])
		{
			if(dis[to[i]]>(ll)dis[u]+val[i])
			{
				dis[to[i]]=dis[u]+val[i];
				q.push((node){dis[to[i]],to[i]});
			}
		}
	}
	return ;
}
void add(int x,int y,int z)
{
	cnt++;
	nxt[cnt]=head[x];
	to[cnt]=y;
	val[cnt]=z;
	head[x]=cnt;
	return ;
}
int main()
{
	int n,m;
	n=read();m=read();s=read();
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		u=read();v=read();w=read();
		add(u,v,w);
	}
	for(int i=1;i<=n;i++)
	{
		dis[i]=inf;
	}
	dijkstra();
	for(int i=1;i<=n;i++)
	{
		printf("%d ",dis[i]);
	}
	return 0;
}
2023/12/27 20:22
加载中...