POJ 3013

Big Christmas Tree

题目链接

解题思路

price of an edge will be (sum of weights of all descendant nodes) × (unit price of the edge).
每条边的代价为孩子节点总重量的和*边的单位代价；
通过分析可知，答案是根节点到（每个节点的最短路径*相对应节点的权重）的和；

注意的点

1. 使用scanf,printf，而不是cin,cout ，节省数据读入，显示的时间；

代码

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define N 50005
long long inf = 0x7fffffffffffffff;
long long ans[N];
int w[N];
int vis[N];
int head[N];
struct Ed{
	int to;
	int c;
	int next; 
	Ed(){}
	Ed(int a,int b):to(a),c(b){
	}
};
Ed edge[N * 2];
int etot;
void addEdge(int u,int v,int w)
{
	edge[etot].to = v;
	edge[etot].c = w;
	edge[etot].next = head[u];
	head[u] = etot++;
	
	edge[etot].to = u;
	edge[etot].c = w;
	edge[etot].next = head[v];
	head[v] = etot++; 
}
struct Nod{
	int id;
	long long c;
	Nod(){}
	Nod(int a,long long b):id(a),c(b){
	}
	bool operator < (const Nod&a)const
	{
		return c > a.c;
	}
};
int n,m;
void init()
{
	etot = 0;
	for(int i = 1; i <= N; ++i)
	{
		vis[i] = 0;
		head[i] = -1;
		ans[i] = inf;
		w[i] = 0;
	}
}
void dij(int s)
{
	Nod tmp,nowd;
	priority_queue<Nod> q;
	ans[s] = 0;
	nowd.c = 0;
	nowd.id = s;
	q.push(nowd);
	int id;
	while(!q.empty())
	{
		nowd = q.top();
		int now = nowd.id;
		q.pop();
		vis[now] = 1;
		if(nowd.c > ans[now])
		{
			continue;
		}
		long long dis;
		for(int i = head[now]; i != -1; i = edge[i].next)
		{
			id = edge[i].to;
			dis = ans[now] + edge[i].c;
			if(!vis[id] && dis < ans[id])
			{
				ans[id] = dis;
				tmp.c =dis;
				tmp.id = id;
				q.push(tmp);
			}
		} 
	}
}
int input()
{
	init();
	cin >> n >> m;
	for(int i = 1; i <= n; ++i)
	{
		scanf("%d",&w[i]);
		//cin >> w[i];
	}
	int u,v, c;
	for(int i = 0; i < m; ++i)
	{
		scanf("%d%d%d",&u,&v,&c);
		//cin >> u >> v >> c;
		addEdge(u,v,c);
	}
	dij(1);
	long long out = 0;
	for(int i = 1;i <= n; ++i)
	{
		if(ans[i] == inf)
		{
			printf("No Answer
");
			return 0;
		}
		out += ans[i] * w[i];
	}
	printf("%lld
",out);
	return 0;
}
int main()
{
	int num;
	scanf("%d",&num);
	for(int i = 0; i < num; ++i)
	{
		input();
	}
	return 0;
}