首页 > 代码库 > POJ Big Christmas Tree(基础最短路)
POJ Big Christmas Tree(基础最短路)
Big Christmas Tree
题目分析:
叫你构造一颗圣诞树,使得 (sum of weights of all descendant nodes) × (unit price of the edge)尽量的小。转换后就是求根节点到每个节点的距离最短,也就是最短路。生成树可能会超时,我没试过。然后,求解最短路要用优化的解法不然会超时。最后的答案就是:sum = w[1] * dist[1] + w[2] * dist[2] + ..... w[n] * dist[n].可以自己推推样例就知道了。
本来是一道简单的最短路。结果因为没有清空,浪费了一个早上的时间。,,,T_T
以后,一定要记住啊!!!血的教训!!!!!
#include <iostream> #include <algorithm> #include <vector> #include <queue> #include <cstdio> #include <cstring> using namespace std; typedef long long LL; const int MAXN = 50000 + 100; struct Edge{ int from,to; LL c; Edge(){}; Edge(int _f,int _t,LL _c) :from(_f),to(_t),c(_c){}; }; vector<Edge> edges; vector<int> G[MAXN]; LL weight[MAXN],dist[MAXN]; bool vst[MAXN]; int numV,numE; //清空 void init(){ edges.clear(); for(int i = 0;i <= numV;++i){ G[i].clear(); } } void addEdge(int x,int y,LL c){ edges.push_back(Edge(x,y,c)); int sz = edges.size(); G[x].push_back(sz - 1); } //松弛操作 bool relax(int u,int v,LL c){ if((dist[u] == -1) || (dist[u] > dist[v] + c)){ dist[u] = dist[v] + c; return true; } return false; } //求解最短路 void spfa(LL src){ int i,u,k; queue<int> Q; for(i = 0;i <= numV;++i){ vst[i] = 0; dist[i] = -1; } Q.push(src); dist[src] = 0; while(!Q.empty()){ u = Q.front(); Q.pop(); vst[u] = 0; for(i = 0;i < (int)G[u].size();++i){ k = G[u][i]; Edge& e = edges[k]; if(relax(e.to,u,e.c) && !vst[e.to]){ vst[e.to] = 1; Q.push(e.to); } } } } int main() { int T; scanf("%d",&T); while(T--){ int x,y; LL c; scanf("%d%d",&numV,&numE); init(); for(int i = 1;i <= numV;++i){ cin >> weight[i]; } for(int i = 0;i < numE;++i){ scanf("%d%d%I64d",&x,&y,&c); addEdge(x,y,c); addEdge(y,x,c); } spfa(1); LL sum = 0; bool flag = false; for(int i = 1;i <= numV;++i){ if(dist[i] == -1){ flag = true; break; } sum += dist[i] * weight[i]; } if(flag) puts("No Answer"); else printf("%I64d\n",sum); } return 0; }
POJ Big Christmas Tree(基础最短路)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。