rp无的蒟

题目传送器!

说好的用prim跑比较快呢？

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+100;
const int M=1e7+100;
int n,m;
inline int read()
{
	int ret=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-')
		{
			f=-1;
		}
		ch=getchar();
	}
	while(isdigit(ch))
	{
		ret=(ret<<1)+(ret<<3)+ch^'0';
		ch=getchar();
	}
	return ret*f;
}
struct edge
{
	int nxt;
	int to;
	int x;
};
edge s[M];
int head[N],tot;
void add(int u,int v,int w)
{
	s[++tot]=(edge){head[u],v,w};
	head[u]=tot;
}
struct node
{
	int h;
	int dis;
	int id;
};
bool operator <(const node &a,const node &b)
{
	if(a.h!=b.h)
	{
		return a.h<b.h;
	}
	return a.dis>b.dis;
}
priority_queue<node> q;
int maxn;
long long cnt,ans;
int g[N],d[N];
bool tree[N];
void prim(int st)
{
	memset(d,0x7f,sizeof(d));
	d[st]=0;
	q.push((node){g[st],0,st});
	while(!q.empty())
	{
		int u=q.top().id;
		q.pop();
		if(tree[u])
		{
			continue;
		}
		tree[u]=true;
		cnt++,ans+=d[u];
		for(int i=head[u];i;i=s[i].nxt)
		{
			int v=s[i].to;
			int w=s[i].x;
			if(tree[v])
			{
				continue;
			}
			if(d[v]>w)
			{
				d[v]=w;
				q.push((node){g[v],d[v],v});
			}
		 } 
	}
}
int main()
{
	n=read();
	m=read();
	for(int i=1;i<=n;i++)
	{
		g[i]=read();
	}
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		u=read();
		v=read();
		w=read();
		if(g[u]>=g[v])
		{
			add(u,v,w);
		}
		if(g[v]>=g[u])
		{
			add(v,u,w);
		}
	}
	prim(1);
	printf("%lld %lld",cnt,ans);
	return 0;
}