记录编号	229900	评测结果	AAAAAAAAAA
题目名称	[省常中2011S4] 聖誕節	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	0.035 s
提交时间	2016-02-20 21:06:28	内存使用	1.75 MiB

//圣诞树(最小生成树） 
 #include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#define maxn 60010
using namespace std;
long long ans=0;
int n,m,nn,head[maxn],dis[maxn],a[maxn],len=0;
bool f[maxn]; 
struct _tree
{
	int to,w,next;
}e[maxn];
struct _lu
{
	int x,dis;
	_lu(){};
	_lu(int a,int b){x=a,dis=b;}
	bool operator < (const _lu &a)const{return a.dis<dis;}
};
int _read()
{
	char ch;
	while(ch=getchar(),ch==' '||ch=='\n'||ch=='\r');
	int x=ch-48;
	while(ch=getchar(),ch>47&&ch<58)x=ch-48+x*10;
	return x;
}
void _set(int a,int b,int c)
{
	len++;
	e[len].to=b;
	e[len].w=c;
	//f[b]=1;
	e[len].next=head[a];
	head[a]=len;
}
void _run();
int main()
{
	freopen("chris.in","r",stdin);
	freopen("chris.out","w",stdout);
	n=_read(),m=_read(),nn=n+1;
	memset(head,0,sizeof(int)*nn);

	f[1]=1;
	for(int i=1;i<=n;i++)
		a[i]=_read();
	for(int i=1;i<=m;i++)
	{
		int a=_read(),b=_read(),c=_read();
		_set(a,b,c);
		_set(b,a,c);
		//e[i].to=b;
		//e[i].w=c;
		//e[i].next=head[a];
		//head[a]=i;
		//f[b]=1;
	}
	/*for(int i=1;i<=n;i++)
	{
		if(f[i]==0)
		{
			puts("No Answer");
			return 0;
		}
		f[i]=0;
	}*/
	_run();//puts("OK");
	for(int i=1;i<=n;i++)
	{
		ans+=dis[i]*a[i];
		//cout<<dis[i]<<' '<<a[i]<<endl;
	} 
		printf("%lld\n",ans);
}
void _run()
{
	priority_queue<_lu>q;
	memset(dis,0x7f,sizeof(int)*nn);
	dis[1]=0;	
	memset(f,0,sizeof(bool)*nn);
	q.push(_lu(1,dis[1]));
	while(!q.empty())
	{  
		_lu topp=q.top();q.pop();
		int top=topp.x;
		if(f[top]==1)continue;
		f[top]=1; 
		//cout<<top<<' '<<dis[top]<<endl;
		for(int i=head[top];i!=0;i=e[i].next)
		{
			int k=e[i].to;
			if(f[k]==0&&dis[k]>dis[top]+e[i].w)
			{
				dis[k]=dis[top]+e[i].w;
				q.push(_lu(k,dis[k]));
			}
		}
	}
}