PKU 1511 Invitation Cards (SPFA+鄰接表)

    題目需要求從原點到所有點的最短距離之和和所有點到原點的最短距離之和，在求所有點到原點最短距離的時候用到了一個技巧：即把圖反向，求原點到所有其他點的最短距離，這樣用一次SPFA就可以將所有點到原點的最短距離求出來了。

        另外也沒什麼好說的，純SPFA。另外用優化到VlogE的dijkstra貌似也能過，有空的時候再寫個。

代碼如下：

#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>
#include <queue>
using namespace std;

#define MAX 1000009
#define INF 1<<30
struct ENode 
{
	int to, cost, next;
} enode[MAX * 4];

int NE = 0;
int OriginHead[MAX], RevHead[MAX];
int dist[MAX];

void insertEdge( int from, int to, int cost )
{
	enode[NE].cost = cost; enode[NE].to = to; enode[NE].next = OriginHead[from]; OriginHead[from] = NE++;
	enode[NE].cost = cost; enode[NE].to = from; enode[NE].next = RevHead[to]; RevHead[to] = NE++;
}

void initDist( int n )
{
	for (int i=0; i<=n; i++) dist[i] = INF;
	dist[1] = 0;
}

int inQueue[MAX];
queue<int> Q;
void SPFA( int *Head )
{
	inQueue[1] = 1;
	Q.push(1);
	while ( ! Q.empty() )
	{
		int q = Q.front();
		Q.pop();
		inQueue[q] = 0;
		for ( int i=Head[q]; i!=-1; i=enode[i].next )
		{
			int e = enode[i].to;
			if ( dist[q] + enode[i].cost < dist[e] ) 
			{
				dist[e] = dist[q] + enode[i].cost;
				if ( !inQueue[e] )
				{
					inQueue[e] = 1;
					Q.push( e );
				}
			}
		}
	}
}

long long getTotal( int n )
{
	long long ret = 0;
	for (int i=2; i<=n; i++)
		ret += dist[i];
	return ret;
}

int main( )
{
	//cout << (int)(1<<30) << endl;
	int T;
	cin >> T;
	
	while( T-- )
	{
		int n, m;
		scanf("%d%d", &n, &m);

		memset( OriginHead, -1, sizeof(OriginHead) );
		memset( RevHead, -1, sizeof(RevHead) );
		NE = 0;
		for (int i=0; i<m; i++)
		{
			int from, to, cost;
			scanf( "%d%d%d", &from, &to, &cost );
			insertEdge( from, to, cost );
		}

		initDist( n );
		memset( inQueue, 0, sizeof(inQueue) );
		SPFA( OriginHead );
		long long int ans = 0;
		ans += getTotal( n );

		//cout << ans << endl;
		initDist( n );
		memset( inQueue, 0, sizeof(inQueue) );
		SPFA( RevHead );
		ans += getTotal( n );

		cout << ans << endl;
	}

	return 0;
}