poj 1511-spfa

poj 1511----spfa

这道题目有点长，看了半天才看懂啥意思。

就是有n个车站，m条路线，每条路线有一个价格。

要求从起始站到每一站，然后再从每一站回去，求最少的钱数。

 

看起来就是最短路径的问题，就是求单源点到其他各点的最但距离（票价），然后建个反向图，求的返回的钱数。加起来就行了。

 

最短路径很多方法，Dijkstra算法，Bell-ford算法，floyd-washall，以及本题目用的spfa算法。

由于数据比较大，Dijkstra算法 （o(n^2)）   floyd-washall(o(n^3))肯定会超时。

 

其实spfa比Dijkstra算法还要简单，代码更少，就是维护一个队列，队列里面放着可能经过的点，知道队列为空。

注意要用邻接表保存图，邻接矩阵会超内存的。

 

代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define nMax 1000010	
#define eMax 10000010
#define inf 1000000010

struct EDGE
{
	int v,w,next;
}edge[nMax], reEdge[nMax];

int nEdge[nMax], nReEdge[nMax];
int n, m, queue[eMax];
__int64 dis[nMax], sum;
bool vis[nMax];

void edgeInit()
{
	for (int i = 1; i <= n; ++ i)
	{
		nEdge[i] = 0;
		nReEdge[i] = 0;
	}
}

void spfaInit()
{
	for (int i = 1; i <= n; ++ i)
	{
		dis[i] = inf;
		vis[i] = false;
	}
}

void spfa(int * nEdge, EDGE * edge)
{
	spfaInit();
	int head = 0, tail = 1;
	dis[1] = 0;
	queue[0] = 1;

	while (head < tail)
	{
		int u = queue[head];
		vis[u] = true;
		int p = nEdge[u];
		while (p != 0)
		{
			int v = edge[p].v, w = edge[p].w;
			if (dis[v] > dis[u] + w)
			{
				dis[v] = dis[u] + w;
				if (!vis[v])
				{
					vis[v] = true;
					queue[tail] = v;
					tail ++;
				}
			}
			p = edge[p].next;
		}
		vis[u] = false;
		head ++;
	}
	for (int i = 1; i <= n; ++ i)
	{
		sum += dis[i];
	}
}

int main()
{
	int t;
	scanf("%d", &t);
	while (t --)
	{
		scanf("%d%d", &n, &m);
		edgeInit();
		for (int i = 1; i <= m; ++ i)
		{
			int u, v, w;
			scanf("%d%d%d", &u, &v, &w);
			edge[i].v = v;
			edge[i].w = w;
			edge[i].next = nEdge[u];
			nEdge[u] = i;

			reEdge[i].v = u;
			reEdge[i].w = w;
			reEdge[i].next = nReEdge[v];
			nReEdge[v] = i;
		}
		sum = 0;
		spfa(nEdge, edge);
		spfa(nReEdge, reEdge);
		printf("%I64d\n", sum);

	}
	return 0;
}