【最短路spfa+记忆化搜索】HDU 1142 A Walk Through the Forest

http://acm.hdu.edu.cn/showproblem.php?pid=1142


Problem Description
Jimmy experiences a lot of stress at work these days, especially since his accident made working difficult. To relax after a hard day, he likes to walk home. To make things even nicer, his office is on one side of a forest, and his house is on the other. A nice walk through the forest, seeing the birds and chipmunks is quite enjoyable.
The forest is beautiful, and Jimmy wants to take a different route everyday. He also wants to get home before dark, so he always takes a path to make progress towards his house. He considers taking a path from A to B to be progress if there exists a route from B to his home that is shorter than any possible route from A. Calculate how many different routes through the forest Jimmy might take.
走AB这条路的前提是: B到home的最短路比A到home的最短路要短，求满足这个要求的office到home的路有多少条

Input
Input contains several test cases followed by a line containing 0. Jimmy has numbered each intersection or joining of paths starting with 1. His office is numbered 1, and his house is numbered 2. The first line of each test case gives the number of intersections N, 1 < N ≤ 1000, and the number of paths M. The following M lines each contain a pair of intersections a b and an integer distance 1 ≤ d ≤ 1000000 indicating a path of length d between intersection a and a different intersection b. Jimmy may walk a path any direction he chooses. There is at most one path between any pair of intersections.

Output
For each test case, output a single integer indicating the number of different routes through the forest. You may assume that this number does not exceed 2147483647

Sample Input
5 6
1 3 2
1 4 2
3 4 3
1 5 12
4 2 34
5 2 24
7 8
1 3 1
1 4 1
3 7 1
7 4 1
7 5 1
6 7 1
5 2 1
6 2 1
0

Sample Output
2
4


我的理解：其实松弛就是判断更新

以下是转的：http://sgeteternal.iteye.com/blog/1148891

SPFA算法系采用队列和松弛技术，每次从队列头取出一点u，对u可直达既点v进行松弛检测，如果松弛成功，检查点v系唔系已经入队列，如果未入，将v压入队列尾，进行以上操作直到队列为空或者有一点进入队列次数为|V|。
SPFA可以代替传统Dijkstra系因为每次只将被松弛点放入队列，当无点被松弛既时候，即每一个d[u] == lo[s, u]。极大程度上减少不必要既松弛操作，速度比传统Dijkstra快

#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <utility>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
//#include <ctime>
#include <ctype.h>
using namespace std;
#define L long long
#define inf 0x3fffffff
#define M 1005

struct road{
	int v, w;
};

int n, dist[M], dp[M];
vector<road> g[M];
bool inq[M];

void spfa (int u)    //spfa求home到各个点的最短路
{
	int i, v, w;
	for (i = 1; i <= n; i++)
	{
		dist[i] = inf;
		inq[i] = false;
	}
	queue<int> q;
	q.push (u);
	dist[u] = 0;
	inq[u] = true;
	while (!q.empty())
	{
		u = q.front();
		q.pop();
		inq[u] = false;
		for (i = 0; i < g[u].size(); i++)
		{
			v = g[u][i].v;
			w = g[u][i].w;
			if (dist[u] + w < dist[v])    //判断是否可以构造出到v的最短路
			{
				dist[v] = dist[u] + w;   //所谓的松弛
				if (!inq[v])
				{
					q.push (v);
					inq[v] = true;
				}
			}
		}
	}
}

int dfs (int u)    //记忆化搜索
{
	if (u == 2)
		return 1;
	if (dp[u] > 0)    //核心
		return dp[u];
	for (int i = 0; i < g[u].size(); i++)
	{
		int v = g[u][i].v;
		if (dist[v] < dist[u])    //满足题意【v相当于B，u相当于A】
			dp[u] += dfs (v);
	}
	return dp[u];
}

int main()
{
	int m, u, v, w, i;
	road x;
	while (scanf ("%d", &n), n)
	{
		for (i = 1; i <= n; i++)
			g[i].clear();
		scanf ("%d", &m);
		while (m--)
		{
			scanf ("%d%d%d", &u, &v, &w);
			x.v = v, x.w = w;
			g[u].push_back (x);
			x.v = u;
			g[v].push_back (x);
		}
		spfa (2);    //逆向思维，把终点当成起点
		memset (dp, 0, sizeof(dp));
		printf ("%d\n", dfs (1));
	}
	return 0;
}