题目大意是:
有一些点,每个点都有一个重量值,然后给出了一些边,每个边都有一个权值
最后让用一些边组成一棵树,使得花费最少,每个边(u,v)的花费=(边得所有子孙节点的重量和)*(该边的权值)
对于这个花费,可以看出,对于每条边(u,v),其花费就相当于每个在后面的结点都走了这个边一次,
那么我们可以假想,已经形成了最优的树,观察这颗树,就能发现,对于一条边(u,v),由于边的子女都走了这条边一次,而且是在一棵树中,那么从根结点到边的某个子女结点的路径必然包含(u,v),其他边同理,那么所有边的花费之和,就可以转化为(从根结点到某个结点的路径长度*结点重量)之和 那么之后就是求最短路径了
那么所有点的最短路径一定是一棵树吗? 这个是显然的 ,因为如果形成环了,到达某个点就出现了多个路径,就要删去长的那条,使其没有环
然后这题需要注意的是,某些地方会超过int,所以开成int64就好了,INF的值也设的大一些。比如100亿,因为最短路径的极限数据应该是5W*2^16>2^31
/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define LOCA
#define MAXN 50005
#define INF 10000000000LL
#define eps 1e-7
using namespace std;
struct node
{
int v;
__int64 w;
node *next;
} edge[MAXN], temp[2 * MAXN];
int n, m, pos;
__int64 d[MAXN];
int q[MAXN * 4];
bool visited[MAXN];
__int64 weight[MAXN];
void spfa(int src, __int64 *ecost) //src是起点, ecost是边权
{
int h, t, u;
node *ptr;
h = 0, t = 1;
memset(visited, 0, sizeof(visited));
q[0] = src;
ecost[src] = 0;
visited[src] = true;
while(h < t)
{
u = q[h++];
visited[u] = false;
ptr = edge[u].next;
while(ptr)
{
if(ecost[ptr -> v] > ecost[u] + ptr -> w)
{
ecost[ptr -> v] = ecost[u] + ptr -> w;
if(!visited[ptr -> v])
{
q[t++] = ptr -> v;
visited[ptr -> v] = true;
}
}
ptr = ptr -> next;
}
}
}
void insert(const int &x, const int &y, const __int64 &w)
{
node *ptr = &temp[pos++];
ptr -> v = y;
ptr -> w = w;
ptr -> next = edge[x].next;
edge[x].next = ptr;
}
void init()
{
pos = 0;
for(int i = 0; i <= n; i++)
{
edge[i].next = NULL;
d[i] = INF;
}
}
int main()
{
int T, u, v;
__int64 w;
scanf("%d", &T);
while(T--)
{
scanf("%d%d", &n, &m);
init();
for(int i = 1; i <= n; i++)
scanf("%I64d", &weight[i]);
for(int i = 0; i < m; i++)
{
scanf("%d%d%I64d", &u, &v, &w);
insert(u, v, w);
insert(v, u, w);
}
spfa(1, d);
int flag = 0;
__int64 ans = 0;
for(int i = 1; i <= n; i++)
{
if(d[i] == INF)
{
flag = 1;
break;
}
ans += weight[i] * d[i];
}
if(flag) printf("No Answer\n");
else printf("%I64d\n", ans);
}
return 0;
}
分享到:
相关推荐
北大POJ2255-Tree Recovery 解题报告+AC代码
poj 2201 Cartesian Tree.md
poj 1909 Marbles on a tree.md
poj 1308 Is It A Tree_.md
北大POJ2525-Text Formalization【TrieTree】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/XW4FQ3
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
Give a tree with n vertices,each edge has a length(positive integer less than 1001). Define dist(u,v)=The min distance between node u and v. Give an integer k,for every pair (u,v) of vertices is ...
北大POJ2513-Colored Sticks【TrieTree+MergeSet+EulerPath】 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ2009年最新版,相当详细.................
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
建树,树的遍历访问,联系数据结构不错的题目
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
POJ1503解答 POJ1503解答,正确答案(已通过POJ)