invitation cards(bellman ford优化).cpp

杭电acm解题报告2001---2099.

//1 <= V,E <= 1000000
//Dijkstra O(V*V) Bellman Ford O(V*E)	〉5s  （TLE）
//Bellman Ford	(优化)   1.46s
//Dijkstra&Heap	   1.24s
//关于Dijkstra的优化：用堆维护使寻找需要扩展的点的过程复杂度降低为1。复杂度大幅降低。
//关于Bellman ford的优化：可以将Bellman ford需要扩展的点放进队列中，扩展顺序有了新的变化
#include <cstdio>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

struct node {
	int e,v;
	node(int a=0,int b=0) {
		e = a;
		v = b;
	}
};
queue<int > SQ;
vector<vector<node> > map;
vector<vector<node> > nmap;
int n,p,q;
int dist[1000100];

int bellman_ford(vector<vector<node> > &path)
{
	int i,j,k,sum,now,l;
	node next;

	while (!SQ.empty()) {
		SQ.pop();
	}
	SQ.push(1);
	dist[1] = 0;

	for (i=0;i<p;i++) {
		l = SQ.size();
		if (l == 0) {
			break;
		}
		while (l--) {
			now = SQ.front();
			SQ.pop();
			for (j=path[now].size()-1;j>=0;j--) {
				next = path[now][j];
				if (dist[now]!=-1 && (dist[next.e]==-1 || dist[next.e] > dist[now]+next.v) ) {
					dist[next.e] = dist[now]+next.v;
					SQ.push(next.e);
				}
			}
		}
	}

	sum = 0;
	for (i=1;i<=p;i++) {
		sum += dist[i];
	}
	return sum;
}

int main()
{
	int i,j,a,b,c;
	scanf("%d",&n);
	while (n--) {
		scanf("%d %d",&p,&q);
		map.resize(p+10);
		nmap.resize(p+10);
		for (i=0;i<=p;i++) {
			map[i].clear();
			nmap[i].clear();
		}
		for (i=0;i<q;i++) {
			scanf("%d %d %d",&a,&b,&c);
			map[a].push_back(node(b,c) );
			nmap[b].push_back(node(a,c) );
		}
		memset(dist,-1,sizeof(dist));
		int ans1 = bellman_ford(map);
		memset(dist,-1,sizeof(dist));
		int ans2 = bellman_ford(nmap);
		printf("%d\n",ans1+ans2);
	}
}