- 浏览: 316227 次
- 性别:
- 来自: 珠海
文章分类
最新评论
-
xialluyouyue:
Ubuntu下搭建nodejs+express+mongodb环境简单教程 -
k317544294:
Good 陈迪峰
(开源游戏) DOTA音效版 俄罗斯方块 -
基德KID.1412:
su1216 写道竖线代表或者,不代表替换
对哦~ 谢谢你的提 ...
正则表达式中特殊字符的用法(收藏) -
su1216:
竖线代表或者,不代表替换
正则表达式中特殊字符的用法(收藏) -
qiqijianglu:
基德KID.1412 写道qiqijianglu 写道基德KI ...
【高斯消元 求期望】HDU 4418 Time travel
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快
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; }
发表评论
-
【生成树计数】HDU 4305 Lightning
2012-08-16 15:45 2682KIDx的解题报告 题 ... -
LOJ 1009 Back to Underworld
2012-01-10 16:50 0KIDx 的解题报告 题目链接:http://ligh ... -
【floyd的灵活运用】LOJ 1174 Commandos
2012-01-10 15:02 1465KIDx的解题报告 题目链接:http://light ... -
HDU 1728 逃离迷宫 + HDU 1072 Nightmare
2011-11-08 18:40 7491KIDx 的解题报告 HDU 1728 逃离迷宫 http:/ ... -
【差分约束(spfa版)】总结
2011-10-05 21:02 7097KIDx 的解题报告 先总结下: 第一: 感觉难点在于建 ... -
【完美匹配-KM算法】HDU总结
2011-10-02 14:35 7194KIDx 的解题报告 题目链接:http://acm.hdu. ... -
【记忆化搜索+最短路】HDU 2833 WuKong
2011-08-28 09:49 2537http://acm.hdu.edu.cn/showprobl ... -
【最短路+枚举】HDU 2962 Trucking【2012-1-20更新】
2011-08-28 09:17 1836KIDx 的解题报告 题目链接:http://acm.hd ... -
【枚举+最短路】HDU 2363 Cycling
2011-08-28 09:07 1802http://acm.hdu.edu.cn/showprobl ... -
【并查集+贪心(或)最短路+二分枚举】HDU 1598
2011-08-27 23:25 4077http://acm.hdu.edu.cn/showprobl ... -
【最短路/3大模板】总结【2012-1-22新增前插的spfa】
2011-08-28 18:15 2929首先献上模板:【点都是默认为从1到n编号,用dijk和f ... -
【HDU、二分匹配、最大匹配/新增1005+1008代码】总结
2011-08-22 14:19 1554KIDx 的解题报告 给出基本定义: 第一题:hdu ... -
【floyd/要防重边】HDU 2923 Einbahnstrasse
2011-08-16 21:48 2337http://acm.hdu.edu.cn/showprobl ... -
【floyd记录路径】HDU 1385 Minimum Transport Cost
2011-08-16 21:26 1966http://acm.hdu.edu.cn/showprobl ... -
【floyd神器】HDU 1217 Arbitrage
2011-08-14 22:09 1786http://acm.hdu.edu.cn/showprobl ... -
【次小生成树】POJ 1679 The Unique MST
2011-08-12 10:00 1039http://poj.org/problem?id=1679 ... -
【拓扑排序】HDU 2647 Reward【2012/3/25更新】
2011-08-11 19:26 1932http://acm.hdu.edu.cn/showprobl ... -
【拓扑排序】HDU 1285 确定比赛名次
2011-08-10 21:38 1160http://acm.hdu.edu.cn/showprobl ... -
【二进制状态压缩+子集枚举/新增深搜】HDU 1557 权利指数
2011-07-28 11:23 2038http://acm.hdu.edu.cn/showprobl ... -
HDU 1175 连连看【2011年11月14号更新】
2011-06-02 17:00 1707http://acm.hdu.edu.cn/showprobl ...
相关推荐
SPFA(Shortest Path Faster Algorithm)是一种基于Bellman-Ford算法改进的求解单源最短路径问题的算法,它利用队列来加速搜索过程,尤其适用于含有大量负权边但不存在负权回路的情况。在本篇文章中,我们将深入探讨...
设施选址算法模型:spfa+最小费用最大流+(二进制粒子群优化算法量子行为粒子群优化算法遗传算法_CodeCraft
最短路SPFA算法。SPFA(Shortest Path Faster Algorithm)算法是求单源最短路径的一种算法,它是Bellman-ford的队列优化,它是一种十分高效的最短路算法。存在负权边时使用。
最短路算法进阶(链式前向星+堆优化+SPFA) 本文主要介绍了最短路算法的进阶知识,包括链式前向星、堆优化和SPFA算法的应用。 一、链式前向星 链式前向星是一种存图方式,用于存储有向图中的边信息。这种存图方式...
队列优化的Bellman-Ford最短路算法(SPFA,Shortest Path Faster Algorithm)是一种在图论中用于寻找有向图中单源最短路径的算法,它是在经典Bellman-Ford算法基础上进行优化得到的。Bellman-Ford算法本身能够处理...
总结来说,SPFA算法是求解带负权边图的最短路径的一种高效方法,虽然在最坏情况下可能不如Bellman-Ford算法稳定,但通常在实践中表现出更好的性能。理解这两种算法的原理和实现细节对于解决图论问题和参加编程竞赛都...
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]; ...
做ACM最短路问题普遍算法的Floyd-Dijkstra-Spfa板子..
C++ SPFA算法 SPFA(Shortest Path Faster Algorithm)是一种求解单源最短路径问题的算法,它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径,并且可以处理负边。该算法的基本思想是使用一个队列来维护...
SPFA(Shortest Path Faster Algorithm)是一种高效的单源最短路算法,广泛应用于图论和动态规划等领域。下面是对SPFA算法的详细介绍和优化。 基本实现 SPFA算法的基本思想是通过relax操作来更新节点的距离值。...
本文将详细介绍四种经典的寻路算法:A*(A-star)、迪杰斯特拉(Dijkstra)、SPFA(Shortest Path Faster Algorithm)以及弗洛伊德(Floyd-Warshall)算法。 首先,我们来看A*算法。A*算法是一种启发式搜索算法,它...
这里是SPFA的源代码
本篇将详细探讨三种解决最短路问题的经典算法:贝尔曼-福特算法(Bellman-Ford)、迪杰斯特拉算法(Dijkstra's Algorithm)以及SPFA(Shortest Path Faster Algorithm)。这些算法广泛应用于路由选择、网络优化和...
在提供的"最短路之SPFA算法.mht"文件中,很可能包含了关于SPFA算法的具体实现、例子以及分析。这个文件可能包含了用编程语言(如C++、Python等)实现的SPFA算法代码,以及通过实例来解释如何运用该算法求解最短路径...
相比于Dijkstra算法,SPFA的优点在于可以处理含有负权边的图,尽管在无负权环的情况下,SPFA的最坏时间复杂度仍为O(V^2),而Dijkstra算法在优先队列的支持下可以达到O(E + V log V)。然而,在实际应用中,SPFA的平均...
相比于Bellman-Ford算法,SPFA在实践中通常更快,但其最坏情况下的时间复杂度仍为O(n^2)。SPFA对于稀疏图,即边的数量远小于节点数量的情况,表现良好。 链式前向星存图是一种常用的图存储结构,它使用邻接表而非...
SPFA 算法是 Bellman-Ford算法 的队列优化算法的别称,通常用于求含负权边的单源最短路径,以及判负权环。SPFA 最坏情况下复杂度和朴素 Bellman-Ford 相同,为 O(VE)。
SPFA最短路径算法 SPFA(Shortest Path Faster Algorithm)是一种单源最短路径算法,它的性能非常好,代码实现也并不复杂。特别是当图的规模大,用邻接矩阵存不下的时候,用 SPFA 则可以很方便地面对临接表。每个...
SPFA(Shortest Path Faster Algorithm)算法是一种求解图中单源最短路径问题的算法,它是Bellman-Ford算法的一种优化版本。在Java中实现SPFA算法,我们需要理解其核心思想并熟悉Java编程语法。 SPFA算法的主要优点...