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 1000000010struct 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;}