Time Limit: 3000MS | Memory Limit: 131072K | |
Total Submissions: 18507 | Accepted: 3947 |
Description
Christmas is coming to KCM city. Suby the loyal civilian in KCM city is preparing a big neat Christmas tree. The simple structure of the tree is shown in right picture.
The tree can be represented as a collection of numbered nodes and some edges. The nodes are numbered 1 through n. The root is always numbered 1. Every node in the tree has its weight. The weights can be different from each other. Also the shape of every available edge between two nodes is different, so the unit price of each edge is different. Because of a technical difficulty, price of an edge will be (sum of weights of all descendant nodes) × (unit price of the edge).
Suby wants to minimize the cost of whole tree among all possible choices. Also he wants to use all nodes because he wants a large tree. So he decided to ask you for helping solve this task by find the minimum cost.
Input
The input consists of T test cases. The number of test cases T is given in the first line of the input file. Each test case consists of several lines. Two numbers v, e (0 ≤ v, e ≤ 50000) are given in the first line of each test case. On the next line, v positive integers wi indicating the weights of v nodes are given in one line. On the following e lines, each line contain three positive integers a, b, c indicating the edge which is able to connect two nodes a and b, and unit price c.
All numbers in input are less than 216.
Output
For each test case, output an integer indicating the minimum possible cost for the tree in one line. If there is no way to build a Christmas tree, print “No Answer” in one line.
Sample Input
2 2 1 1 1 1 2 15 7 7 200 10 20 30 40 50 60 1 2 1 2 3 3 2 4 2 3 5 4 3 7 2 3 6 3 1 5 9
Sample Output
15 1210
Source
思路:求出各点的最短路径 再与点的重量相乘之和; 注意两点我觉得,inf 要定义足够大,10个9吧,还有,用memset 初始化会严重超时,不用竟然才600多MS 。。。
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; const int VM=50010; const int EM=50010; const long long INF=1e11; int n,m,cnt,head[VM]; int weight[VM],vis[VM]; long long dis[VM]; struct Edge{ int to,nxt; long long cap; }edge[VM<<1]; void addedge(int cu,int cv,long long cw){ edge[cnt].to=cv; edge[cnt].cap=cw; edge[cnt].nxt=head[cu]; head[cu]=cnt++; edge[cnt].to=cu; edge[cnt].cap=cw; edge[cnt].nxt=head[cv]; head[cv]=cnt++; } void SPFA(){ queue<int> q; while(!q.empty()) q.pop(); for(int i=1;i<=n;i++){ dis[i]=INF; vis[i]=0; } dis[1]=0; vis[1]=1; q.push(1); while(!q.empty()){ int u=q.front(); q.pop(); vis[u]=0; for(int i=head[u];i!=-1;i=edge[i].nxt){ int v=edge[i].to; if(dis[v]>dis[u]+edge[i].cap){ dis[v]=dis[u]+edge[i].cap; if(!vis[v]){ vis[v]=1; q.push(v); } } } } } int main(){ //freopen("input.txt","r",stdin); int t; scanf("%d",&t); while(t--){ cnt=0; memset(head,-1,sizeof(head)); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&weight[i]); int u,v; long long w; while(m--){ scanf("%d%d%lld",&u,&v,&w); addedge(u,v,w); } if(n==0 || n==1){ printf("0\n"); continue; } SPFA(); long long ans=0; for(int i=1;i<=n;i++){ if(dis[i]==INF){ ans=-1; break; } ans+=weight[i]*dis[i]; } if(ans==-1) printf("No Answer\n"); else printf("%lld\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解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)