`

【最短路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;
}
  • 大小: 39.2 KB
1
10
分享到:
评论

相关推荐

    最短路SPFA

    SPFA(Shortest Path Faster Algorithm)是一种基于Bellman-Ford算法改进的求解单源最短路径问题的算法,它利用队列来加速搜索过程,尤其适用于含有大量负权边但不存在负权回路的情况。在本篇文章中,我们将深入探讨...

    设施选址算法模型:spfa+最小费用最大流+(二进制粒子群优化算法量子行为粒子群优化算法遗传算法_CodeCraft.zip

    设施选址算法模型:spfa+最小费用最大流+(二进制粒子群优化算法量子行为粒子群优化算法遗传算法_CodeCraft

    SPFA.cpp SPFA算法

    最短路SPFA算法。SPFA(Shortest Path Faster Algorithm)算法是求单源最短路径的一种算法,它是Bellman-ford的队列优化,它是一种十分高效的最短路算法。存在负权边时使用。

    最短路课件(链式前向星+堆优化+SPFA)

    最短路算法进阶(链式前向星+堆优化+SPFA) 本文主要介绍了最短路算法的进阶知识,包括链式前向星、堆优化和SPFA算法的应用。 一、链式前向星 链式前向星是一种存图方式,用于存储有向图中的边信息。这种存图方式...

    队列优化的Bellmanford最短路算法(SPFA)C++实现

    队列优化的Bellman-Ford最短路算法(SPFA,Shortest Path Faster Algorithm)是一种在图论中用于寻找有向图中单源最短路径的算法,它是在经典Bellman-Ford算法基础上进行优化得到的。Bellman-Ford算法本身能够处理...

    图论,ACM SPFA 和Bellman_ford.ppt 最短路算法

    总结来说,SPFA算法是求解带负权边图的最短路径的一种高效方法,虽然在最坏情况下可能不如Bellman-Ford算法稳定,但通常在实践中表现出更好的性能。理解这两种算法的原理和实现细节对于解决图论问题和参加编程竞赛都...

    SPFA+Dijkstra+Floyd Java模板

    SPFA import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class SPFA { static SE[] e = new SE[9999]; static int[] dis = new int[9999]; ...

    最短路的Floyd-Dijkstra-Spfa板子

    做ACM最短路问题普遍算法的Floyd-Dijkstra-Spfa板子..

    c++ SPFA算法

    C++ SPFA算法 SPFA(Shortest Path Faster Algorithm)是一种求解单源最短路径问题的算法,它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径,并且可以处理负边。该算法的基本思想是使用一个队列来维护...

    SPFA算法优化及应用

    SPFA(Shortest Path Faster Algorithm)是一种高效的单源最短路算法,广泛应用于图论和动态规划等领域。下面是对SPFA算法的详细介绍和优化。 基本实现 SPFA算法的基本思想是通过relax操作来更新节点的距离值。...

    A星,迪杰斯特拉,SPFA,弗洛伊德寻路算法

    本文将详细介绍四种经典的寻路算法:A*(A-star)、迪杰斯特拉(Dijkstra)、SPFA(Shortest Path Faster Algorithm)以及弗洛伊德(Floyd-Warshall)算法。 首先,我们来看A*算法。A*算法是一种启发式搜索算法,它...

    SPFA算法源代码

    这里是SPFA的源代码

    最短路模板(详细注解)

    本篇将详细探讨三种解决最短路问题的经典算法:贝尔曼-福特算法(Bellman-Ford)、迪杰斯特拉算法(Dijkstra's Algorithm)以及SPFA(Shortest Path Faster Algorithm)。这些算法广泛应用于路由选择、网络优化和...

    SPFA.rar_SPFA

    在提供的"最短路之SPFA算法.mht"文件中,很可能包含了关于SPFA算法的具体实现、例子以及分析。这个文件可能包含了用编程语言(如C++、Python等)实现的SPFA算法代码,以及通过实例来解释如何运用该算法求解最短路径...

    SPFA.zip_SPFA

    相比于Dijkstra算法,SPFA的优点在于可以处理含有负权边的图,尽管在无负权环的情况下,SPFA的最坏时间复杂度仍为O(V^2),而Dijkstra算法在优先队列的支持下可以达到O(E + V log V)。然而,在实际应用中,SPFA的平均...

    最短路全家桶(Floyd,Dijkstra,SPFA)

    相比于Bellman-Ford算法,SPFA在实践中通常更快,但其最坏情况下的时间复杂度仍为O(n^2)。SPFA对于稀疏图,即边的数量远小于节点数量的情况,表现良好。 链式前向星存图是一种常用的图存储结构,它使用邻接表而非...

    SPFA带负权的最短路径算法

    SPFA 算法是 Bellman-Ford算法 的队列优化算法的别称,通常用于求含负权边的单源最短路径,以及判负权环。SPFA 最坏情况下复杂度和朴素 Bellman-Ford 相同,为 O(VE)。

    最短路径 之 SPFA算法

    SPFA最短路径算法 SPFA(Shortest Path Faster Algorithm)是一种单源最短路径算法,它的性能非常好,代码实现也并不复杂。特别是当图的规模大,用邻接矩阵存不下的时候,用 SPFA 则可以很方便地面对临接表。每个...

    spfa算法的java实现

    SPFA(Shortest Path Faster Algorithm)算法是一种求解图中单源最短路径问题的算法,它是Bellman-Ford算法的一种优化版本。在Java中实现SPFA算法,我们需要理解其核心思想并熟悉Java编程语法。 SPFA算法的主要优点...

Global site tag (gtag.js) - Google Analytics