本文主要是介绍poj 3031 Big Christmas Tree(水spfa)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://poj.org/problem?id=3013
题意：
Because of a technical difficulty, price of an edge will be (sum of weights of all descendant nodes) × (unit price of the edge).这句话一直没看懂。后面还以为是最小生成树。
正确题意是：给一个无向图，计算每个点到1节点的最短路径(dis[i]) * 每个节点的weights之和。
注意：边权值等要用__int64;无向图；
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#define LL long long
#define _LL __int64
using namespace std;
const _LL INF = 1e18;
const int maxn = 50010;
const int maxm = 50010;struct node
{int v;_LL w;int next;
}edge[2*maxm];int cnt,head[maxn];
_LL W[maxn];
int n,m;
_LL ans,dis[maxn];void init()
{cnt = 0;memset(head,-1,sizeof(head));
}void add(int u, int v, _LL w)
{edge[cnt] = (struct node){v,w,head[u]};head[u] = cnt++;
}void solve()
{int inque[maxn];queue <int> que;while(!que.empty()) que.pop();memset(inque,0,sizeof(inque));for(int i = 1; i <= n; i++)dis[i] = INF;dis[1] = 0;inque[1] = 1;que.push(1);while(!que.empty()){int u = que.front();que.pop();inque[u] = 0;for(int i = head[u]; i != -1; i = edge[i].next){int v = edge[i].v;_LL w = edge[i].w;if(dis[v] > dis[u] + w){dis[v] = dis[u] + w;if(!inque[v]){inque[v] = 1;que.push(v);}}}}
}int main()
{int test;int u,v;_LL w;scanf("%d",&test);while(test--){init();scanf("%d %d",&n,&m);for(int i = 1; i <= n; i++)scanf("%I64d",&W[i]);for(int i = 1; i <= m; i++){scanf("%d %d %I64d",&u,&v,&w);add(u,v,w);add(v,u,w);}solve();ans = 0;bool flag = true;for(int i = 2; i <= n; i++){if(dis[i] == INF){flag = false;break;}ans += dis[i] * W[i];}if(flag == false)printf("No Answer\n");else printf("%I64d\n",ans);}return 0;
}
这篇关于poj 3031 Big Christmas Tree(水spfa)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
