记录编号	581177	评测结果	AAAAAAAAAA
题目名称	[省常中2011S4] 聖誕節	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.044 s
提交时间	2023-07-30 17:46:32	内存使用	1.91 MiB

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
const int N = 50010,M = 100010;
//M的值要定义到两倍，因为是无向图，要存两条边!!!
//!!!
//!!!
//M的值要定义到两倍，因为是无向图，要存两条边!!!
int n,m;
long long a[N];
struct made{
	long long ver,ed,nx;
}e[M];
long long hd[N],v[N],d[N],tot;
long long ans;
void add_(int x,int y,int z){
	tot++;
	e[tot].ver = y,e[tot].ed = z,e[tot].nx = hd[x],hd[x] = tot;
}
void dij(int x){
	memset(v,0,sizeof(v));
	for(int i = 1;i <= n;i++)d[i] = INT_MAX;
	priority_queue<P,vector<P>,greater<P> >q;
	d[x] = 0;
	q.push(make_pair(d[x],x));
	while(!q.empty()){
		int x = q.top().second;q.pop();
		if(v[x])continue;
		v[x] = 1;
		for(int i = hd[x];i;i = e[i].nx){
			long long y = e[i].ver,z = e[i].ed;
			if(d[x] + z < d[y]){
				d[y] = d[x] + z;
				q.push(make_pair(d[y],y));
			}
		}
	}
}
int main(){
	freopen("chris.in","r",stdin);
	freopen("chris.out","w",stdout);
	//对于每个节点i(根节点1除外)它的重分别与1至i的路径中每条边的价值相乘
	//所以只需要寻找1至i的最短路，与i的重相乘，再全部相加可得结果 
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;i++){
		scanf("%lld",&a[i]);
	}
	for(int i = 1;i <= m;i++){
		long long x,y,z;
		scanf("%lld%lld%lld",&x,&y,&z);
		add_(x,y,z);
		add_(y,x,z);
	}
	dij(1);
	for(int i = 1;i <= n;i++){
		if(d[i] == INT_MAX){
			printf("No Answer\n");
			return 0;
		}
		else ans += 1LL * d[i] * a[i];
	}
	printf("%lld\n",ans);
	
	return 0;
	
}