为什么还是会TLE啊啊啊
查看原帖
为什么还是会TLE啊啊啊
377511
果圆楼主2021/5/11 17:11
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=200010;
int dis[N],to[N],next[N],w[N],h[N];
bool wd[N];
int u,ans;
inline void rd(int &x)
{
	x=0;int f=1;char c=getchar();
	while((c<'0'||c>'9')&&c!='-') c=getchar();
	if(c=='-') f=-1,c=getchar();
	while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	x*=f;
}
void add(int a,int b,int c)
{
	u++;
	w[u]=c;
	to[u]=b;
	next[u]=h[a];
	h[a]=u;
}
int main()
{
	int n,m;
	rd(n),rd(m);
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		rd(a),rd(b),rd(c);
		add(a,b,c);
		add(b,a,c);
	}
	memset(dis,0x3f,sizeof dis);
	dis[1]=0;
	for(int k=1;k<=n;k++)
	{
		int p=0x3f3f3f,t=0;
		for(int i=1;i<=n;i++)
		{
			if(!wd[i]&&dis[i]<p)
			{
				p=dis[i];
				t=i;
			}
		}
		if(p==0x3f3f3f) 
		{
			puts("orz");
			return 0;
		}
		wd[t]=1;
		ans+=dis[t];
	    for(int i=h[t];i;i=next[i])
	    {
	    	int z=to[i];
	    	dis[z]=min(dis[z],w[i]);
		}
	}
	cout<<ans;
	return 0;
}
2021/5/11 17:11
加载中...