big christmas tree(最短路).cpp

杭电acm解题报告2001---2099.

//可以发现cost总和是该点权×根到该点距离
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

typedef __int64 int64;
const int MAX = 50100;
struct node {
	int64 t,cost;
	node(int64 x,int64 y) : t(x), cost(y) {}
	bool operator < (const node & tt) const {
		return cost > tt.cost;
	}
};
vector<node> path[MAX];
int64 dist[MAX];
int v, e, w[MAX];

int64 Dijkstra() {
	int i,j;
	int64 allcost;
	priority_queue<node> pq;
	allcost = 0;
	for(i=0;i<=v;i++) dist[i] = LLONG_MAX;
	dist[1] = -1;
	for(i=0;i<path[1].size();i++) pq.push(node(path[1][i].t, path[1][i].cost));
	while(!pq.empty()) {
		node now = pq.top();
		pq.pop();
		if(dist[now.t] == -1) continue;
		dist[now.t] = -1;
		allcost += now.cost * w[now.t];//权×根到该点距离
		for(i=0;i<path[now.t].size();i++) {
			node e = path[now.t][i];
			if(dist[e.t] != -1 && dist[e.t] > now.cost + e.cost) {
				dist[e.t] = now.cost + e.cost;
				pq.push(node(e.t, dist[e.t]));
			}
		}
	}
	for(i=1;i<=v;i++) {
		if(dist[i] != -1) return -1;
	}
	return allcost;
}

int main() {
	int t,i,j;
	//printf("%I64d\n", LLONG_MAX);
	scanf("%d", &t);
	while(t --) {
		scanf("%d %d", &v,&e);
		for(i=1;i<=v;i++) {
			scanf("%d", w+i);
			path[i].clear();
		}
		while(e --) {
			int x,y,z;
			scanf("%d %d %d", &x,&y,&z);
			if(x == y) continue;
			path[x].push_back(node(y,z));
			path[y].push_back(node(x,z));
		}
		int64 cv = Dijkstra();
		printf(cv == -1 ? "No Answer\n" : "%I64d\n", cv);
	}
}