【最短路spfa+记忆化搜索】HDU 1142 A Walk Through the Forest_C/C++_编程开发_程序员俱乐部

#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;
}

• 
• 大小: 39.2 KB

• 查看图片附件