POJ 3013 Big Christmas Tree(最短路Dijkstra+优先队列优化，SPFA)

ACM

题目地址：POJ 3013

题意： 

圣诞树是由n个节点和e个边构成的，点编号1-n。树根为编号1，选择一些边。使得全部节点构成一棵树。选择边的代价是（子孙的点的重量）×（这条边的价值）。

求代价最小多少。

分析： 

单看每一个点被计算过的代价，非常明显就是从根到节点的边的价值。所以这是个简单的单源最短路问题。

只是坑点还是非常多的。

点的数量高达5w个，用矩阵存不行。仅仅能用边存。 

还有路径和结果会超int。所以要提高INF的上限。(1<<16)*50000就可以。

能够用Dijkstra+优先队列做，也能够用SPFA做，貌似SPFA会更快。我这里用的是Dijkstra，要1s多...回头要用SPFA做一遍。

用SPFA做了一遍发现也是1s多，看了是STL用多了 = =。 

嘛。留个模板。

代码： 

(Dijkstra+priority_queue)

/*

*  Author:      illuz <iilluzen[at]gmail.com>

*  File:        3013.cpp

*  Create Date: 2014-07-27 09:54:35

*  Descripton:  dijkstra

*/

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#include <vector>

#include <queue>

#define repf(i,a,b) for(int i=(a);i<=(b);i++)

const int N = 50100;

const long long INF = (long long)(1<<16)*N;

struct Edge {

	int from, to;

	int dist;

};

struct HeapNode {

	int d;

	int u;

	bool operator < (const HeapNode rhs) const {

		return d > rhs.d;

	}

};

struct Dijkstra {

	int n, m;			// number of nodes and edges

	vector<Edge> edges;

	vector<int> G[N];	// graph

	bool vis[N];	// visited?

long long d[N];		// dis

	int p[N];		// prevent edge

	void init(int _n) {

		n = _n;

	}

	void relief() {

		for (int i = 0; i < n; i++) {

			G[i].clear();

		}

		edges.clear();

	}

	void AddEdge(int from, int to, int dist) {

		// if non-directed, add twice

		edges.push_back((Edge){from, to, dist});

		m = edges.size();

		G[from].push_back(m - 1);

	}

	void dijkstra(int s) {

		priority_queue<HeapNode> Q;

		for (int i = 0; i < n; i++) {

			d[i] = INF;

			vis[i] = 0;

		}

		d[s] = 0;

		Q.push((HeapNode){0, s});

		while (!Q.empty()) {

			HeapNode x = Q.top();

			Q.pop();

			int u = x.u;

			if (vis[u]) {

				continue;

			}

			vis[u] = true;

			for (int i = 0; i < G[u].size(); i++) {	// update the u's linking nodes

				Edge& e = edges[G[u][i]];	//ref for convenient

				if (d[e.to] > d[u] + e.dist) {

					d[e.to] = d[u] + e.dist;

					p[e.to] = G[u][i];

					Q.push((HeapNode){d[e.to], e.to});

				}

			}

		}

	}

};

int t;

int e, v, x, y, d, w[N];

int main() {

	scanf("%d", &t);

	Dijkstra di;

	while (t--) {

		scanf("%d%d", &v, &e);

		di.init(v);

		repf (i, 0, v - 1) {

			scanf("%d" ,&w[i]);

		}

		repf (i, 0, e - 1) {

			scanf("%d%d%d", &x, &y, &d);

			di.AddEdge(x - 1, y - 1, d);

			di.AddEdge(y - 1, x - 1, d);

		}

		di.dijkstra(0);

		long long ans = 0;

		bool ring = false;

		repf (i, 0, v - 1) {

			if (di.d[i] == INF) {

				ring = true;

			}

			ans += w[i] * di.d[i];

		}

		if (ring) {

			cout << "No Answer" << endl;

		} else {

			cout << ans << endl;

		}

		if (t)	// if not the last case

			di.relief();

	}

	return 0;

}

(SPFA)

/*

*  Author:      illuz <iilluzen[at]gmail.com>

*  File:        3013_spfa.cpp

*  Create Date: 2014-07-27 15:44:45

*  Descripton:  spfa

*/

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#include <vector>

#include <queue>

#define repf(i,a,b) for(int i=(a);i<=(b);i++)

const int N = 50100;

const long long INF = (long long)(1<<16)*N;

struct Edge {

	int from, to;

	int spst;

};

struct SPFA {

	int n, m;

	vector<Edge> edges;

	vector<int> G[N];	// the edges which from i

	bool vis[N];

	long long d[N];	// sps

	int p[N];		// prevent

	void init(int _n) {

		n = _n;

	}

	void relief() {

		for (int i = 0; i < n; i++)

			G[i].clear();

		edges.clear();

	}

	void AddEdge(int from, int to, int spst) {

		// if non-sprected, add twice

		edges.push_back((Edge){from, to, spst});

		m = edges.size();

		G[from].push_back(m - 1);

	}

	void spfa(int s) {

		queue<int> Q;

		while (!Q.empty())

			Q.pop();

		for (int i = 0; i < n; i++) {

			d[i] = INF;

			vis[i] = 0;

		}

		d[s] = 0;

		vis[s] = 1;

		Q.push(s);

		while (!Q.empty()) {

			int u = Q.front();

			Q.pop();

			vis[u] = 0;

			for (int i = 0; i < G[u].size(); i++) {

				Edge& e = edges[G[u][i]];

				if (d[e.to] > d[u] + e.spst) {

					d[e.to] = d[u] + e.spst;

					p[e.to] = G[u][i];

					if (!vis[e.to]) {

						vis[e.to] = 1;

						Q.push(e.to);

					}

				}

			}

		}

	}

};

int t;

int e, v, x, y, d, w[N];

int main() {

	scanf("%d", &t);

	SPFA sp;

	while (t--) {

		scanf("%d%d", &v, &e);

		sp.init(v);

		repf (i, 0, v - 1) {

			scanf("%d" ,&w[i]);

		}

		repf (i, 0, e - 1) {

			scanf("%d%d%d", &x, &y, &d);

			sp.AddEdge(x - 1, y - 1, d);

			sp.AddEdge(y - 1, x - 1, d);

		}

		sp.spfa(0);

		long long ans = 0;

		bool ring = false;

		repf (i, 0, v - 1) {

			if (sp.d[i] == INF) {

				ring = true;

			}

			ans += w[i] * sp.d[i];

		}

		if (ring) {

			cout << "No Answer" << endl;

		} else {

			cout << ans << endl;

		}

		if (t)	// if not the last case

			sp.relief();

	}

	return 0;

}