POJ 1511 Invitation Cards SPFA算法例题

POJ 1511 Invitation Cards SPFA算法题解

本算法就是Bellman-ford的改进，SPFA即 Shortest Path Faster Algorithm.

解析这个算法的博文不少，不过没有什么好的证明。

我觉得这个算法之所以正确，是因为每次新增加一个所谓的松弛点，那么其他任何点值可能以该松弛点为中介点，才可能找到比原来更加短的路径，故此是正确的。

当然这个不是正规的证明。不过仔细想想这个算法，的确是巧妙，而他的妙点，就是这里了。

解析和图参考这个博客的吧，我懒得转帖了：http://blog.****.net/muxidreamtohit/article/details/7894298

下面使用vector容器建立邻接矩阵，不过应该是使用静态数组的邻接矩阵会比这个方法快。使用vector是因为这样思路会更加清晰点。

#include <stdio.h>
#include <iostream>
#include <queue>
#include <set>
#include <vector>
#include <limits.h>
#include <string.h>
#include <stack>
#include <algorithm>
using namespace std;

const int MAX_N = 1000001;
struct Edge
{
	int des, w;
	Edge(int d, int w1):des(d), w(w1){}
};
vector<Edge> gra[MAX_N];
int srcArr[MAX_N], desArr[MAX_N], wei[MAX_N], dist[MAX_N];
bool vis[MAX_N];
int P, Q;	//vectices and edges number

void initGra(int src[], int des[])
{
	for (int i = 1; i <= P; i++) gra[i].clear();
	for (int i = 0; i < Q; i++)
		gra[src[i]].push_back(Edge(des[i], wei[i]));
}

void SPFA()
{
	fill(dist, dist+P+1, INT_MAX);
	memset(vis, 0, sizeof(bool) * (P+1));
	dist[1] = 0;
	stack<int> stk;//使用set超时set<int> si;	//直接代替vis和queue的功能
	stk.push(1);
	vis[1] = true;
	
	while (!stk.empty())
	{
		int u = stk.top();
		stk.pop();
		vis[u] = false; //记录出列

		for (size_t i = 0; i < gra[u].size(); i++)
		{
			int v = gra[u][i].des;
			if (dist[u] + gra[u][i].w < dist[v])
			{
				dist[v] = dist[u] + gra[u][i].w;
				if (!vis[v])
				{
					vis[v] = true;
					stk.push(v);
				}
			}
		}
	}
}

int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d %d", &P, &Q);
		for (int i = 0; i < Q; i++)
		{
			scanf("%d %d %d", &srcArr[i], &desArr[i], &wei[i]);
		}

		initGra(srcArr, desArr);
		SPFA();
		long long ans = 0;
		for (int i = 1; i <= P; i++) ans += dist[i];
		
		initGra(desArr, srcArr);
		SPFA();
		for (int i = 1; i <= P; i++) ans += dist[i];

		printf("%lld\n", ans);
	}
	return 0;
}