- 浏览: 309295 次
- 性别:
- 来自: 珠海
文章分类
最新评论
-
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 2634KIDx的解题报告 题 ... -
LOJ 1009 Back to Underworld
2012-01-10 16:50 0KIDx 的解题报告 题目链接:http://ligh ... -
【floyd的灵活运用】LOJ 1174 Commandos
2012-01-10 15:02 1435KIDx的解题报告 题目链接:http://light ... -
HDU 1728 逃离迷宫 + HDU 1072 Nightmare
2011-11-08 18:40 7458KIDx 的解题报告 HDU 1728 逃离迷宫 http:/ ... -
【差分约束(spfa版)】总结
2011-10-05 21:02 7002KIDx 的解题报告 先总结下: 第一: 感觉难点在于建 ... -
【完美匹配-KM算法】HDU总结
2011-10-02 14:35 7136KIDx 的解题报告 题目链接:http://acm.hdu. ... -
【记忆化搜索+最短路】HDU 2833 WuKong
2011-08-28 09:49 2499http://acm.hdu.edu.cn/showprobl ... -
【最短路+枚举】HDU 2962 Trucking【2012-1-20更新】
2011-08-28 09:17 1801KIDx 的解题报告 题目链接:http://acm.hd ... -
【枚举+最短路】HDU 2363 Cycling
2011-08-28 09:07 1767http://acm.hdu.edu.cn/showprobl ... -
【并查集+贪心(或)最短路+二分枚举】HDU 1598
2011-08-27 23:25 4030http://acm.hdu.edu.cn/showprobl ... -
【最短路/3大模板】总结【2012-1-22新增前插的spfa】
2011-08-28 18:15 2874首先献上模板:【点都是默认为从1到n编号,用dijk和f ... -
【HDU、二分匹配、最大匹配/新增1005+1008代码】总结
2011-08-22 14:19 1518KIDx 的解题报告 给出基本定义: 第一题:hdu ... -
【floyd/要防重边】HDU 2923 Einbahnstrasse
2011-08-16 21:48 2297http://acm.hdu.edu.cn/showprobl ... -
【floyd记录路径】HDU 1385 Minimum Transport Cost
2011-08-16 21:26 1933http://acm.hdu.edu.cn/showprobl ... -
【floyd神器】HDU 1217 Arbitrage
2011-08-14 22:09 1750http://acm.hdu.edu.cn/showprobl ... -
【次小生成树】POJ 1679 The Unique MST
2011-08-12 10:00 1014http://poj.org/problem?id=1679 ... -
【拓扑排序】HDU 2647 Reward【2012/3/25更新】
2011-08-11 19:26 1903http://acm.hdu.edu.cn/showprobl ... -
【拓扑排序】HDU 1285 确定比赛名次
2011-08-10 21:38 1124http://acm.hdu.edu.cn/showprobl ... -
【二进制状态压缩+子集枚举/新增深搜】HDU 1557 权利指数
2011-07-28 11:23 1989http://acm.hdu.edu.cn/showprobl ... -
HDU 1175 连连看【2011年11月14号更新】
2011-06-02 17:00 1664http://acm.hdu.edu.cn/showprobl ...
相关推荐
SPFA入门,很好的入门指南。值得一下!
最短路课件(链式前向星+堆优化+SPFA)
最短路无向图spfa+slm优化,可作为模板使用
最短路SPFA算法。SPFA(Shortest Path Faster Algorithm)算法是求单源最短路径的一种算法,它是Bellman-ford的队列优化,它是一种十分高效的最短路算法。存在负权边时使用。
使用C++实现的Queue improved Bellman-Ford单源最短路算法,在国内还被叫做SPFA。这个程序输入一个图,找到图中的一个点,这个点到最远点的长度最短。图使用邻接表保存。
这里面的内容是个PPT,介绍的很好,如果你想更加的清楚 SPFA 和Bellman_ford.ppt 最短路算法的原理,这是个不错的选择
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板子..
最短路全家桶(Floyd,Dijkstra,SPFA)量大管饱
图论- 最短路- Bellman-Ford 算法与 SPFA.rar
这里是SPFA的源代码
最短路之SPFA算法.rar。。。算法复分析及例题设计,综合分析
SPFA——Shortest Path Faster Algorithm,它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径,可以处理负边。
SPFA 算法是 Bellman-Ford算法 的队列优化算法的别称,通常用于求含负权边的单源最短路径,以及判负权环。SPFA 最坏情况下复杂度和朴素 Bellman-Ford 相同,为 O(VE)。
基本思想 用一个队列来进行维护。初始时将源加入队列。每次从队列中取出一个元素,并对所有与他相邻的点进行松弛,若某个相邻的点松弛成功,则将其入队。...d[i]:起点s到i的临时最短路长度 松驰的结果是使j的d值减小
SPFA算法模版+邻接表实现.docx
求单源最短路的SPFA算法的全称是:Shortest Path Faster Algorithm。 这个是自己写的,思想还是一样发的。
自己打的spfa算法板子。包含邻接表的两种形式,邻接矩阵Map;此代码不完全,(使用是要注释掉部分的)在使用时要结合题意更改。望采纳!
求单源最短路的SPFA算法的全称是:Shortest Path Faster Algorithm。 SPFA算法是西南交通大学段凡丁于1994年发表的. 从名字我们就可以看出,这种算法在效率上一定有过人之处。 很多时候,给定的图存在负权边,这时...
SPFA算法优化及应用,SPFA算法优化及应用,SPFA算法优化及应用