• 板块灌水区
  • 楼主SunXiaoping
  • 当前回复19
  • 已保存回复19
  • 发布时间2021/4/18 21:38
  • 上次更新2023/11/5 00:21:51
查看原帖
478528
SunXiaoping楼主2021/4/18 21:38

为什么CE:

#include<bits/stdc++.h>
using namespace std;
inline long long read()
{
   long long s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
inline void write(long long x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
const long long maxn=2e5+5;
long long dis[maxn],head[maxn],eid=1,n,m,u,v,w,vis[maxn];
struct node
{
	long long v,next,w;
}e[maxn];
inline void insert(long long u,long long v,long long w)
{
	e[eid].v=v;
	e[eid].next=head[u];
	e[eid].w=w;
	head[u]=eid++;
}
struct cmp
{
	bool operator()(node a,node b)
	{
		return a.w>b.w;
	}
};
inline void Dijkstra(long long s)
{
	for(int i=1;i<=200000;i++)
	{
		dis[i]=0x7fffffff;
	}
	dis[s]=0;
	priority_queue<long long,vector<long long>,cmp> Q;
	while(!Q.empty())Q.pop();
	Q.push(s);
	while(!Q.empty())
	{
		long long u=Q.top();
		Q.pop();
		if(!vis[u])
		{
			vis[u]=1;
			for(long long i=head[u];i;i=e[i].next)
			{
				long long v=e[i].v;
				dis[v]=min(dis[v],dis[u]+e[i].w);
				Q.push(v);
			}
		}
	}
	return;
}
int main()
{
	n=read();
	m=read();
	for(long long i=1;i<=m;i++)
	{
		u=read();
		v=read();
		w=read();
		insert(u,v,w);
		insert(v,u,w);
	}
	Dijkstra(1);
	for(long long i=1;i<=n;i++)
	{
		write(dis[i]);
		putchar(' ');
	}
}

https://www.luogu.com.cn/discuss/show/311962

2021/4/18 21:38
加载中...