A Walk Through the Forest
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2183 Accepted Submission(s): 787
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.
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
题目大意:寻找一共有多少条符合题意的路。能够从点A走到点B的要求是:点A到终点的最短路 > 点B到终点的最短路。 也就是说:从终点出发,求每一个点的最短路,然后那些最短路的值记录起来,作为能否通过的判断条件。最后用记忆化搜索来搜索出一共多少条符合要求的路。普通的dfs是超时的,bfs是超内存的。
链接:http://acm.hdu.edu.cn/showproblem.php?pid=1142
代码:
#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <queue>
#include <vector>
using namespace std;
const int INF = 99999999;
const int N = 1005;
vector<int> road[N]; //定义一个向量(第一次用-O(∩_∩)O-)
int map[N][N], dist[N], s[N];
bool visit[N];
int n, t, sum;
void init()
{
int i, j;
sum = 0;
memset(s, 0, sizeof(s));
for(i = 0; i <= n; i++) road[i].clear();
for(i = 0; i <= n; i++)
for(j = 0; j <= n; j++)
if(i == j) map[i][j] = 0;
else map[i][j] = INF;
}
void input()
{
int a, b, d;
while(t--)
{
scanf("%d %d %d", &a, &b, &d);
if(d < map[a][b])
{
map[a][b] = map[b][a] = d; //双向的
road[a].push_back(b);
road[b].push_back(a);
}
}
}
void spfa() //比较喜欢用spfa
{
int i, now;
memset(visit, false, sizeof(visit));
for(i = 1; i <= n; i++) dist[i] = INF;
dist[2] = 0;
queue<int> Q;
Q.push(2);
visit[2] = true;
while(!Q.empty())
{
now = Q.front();
Q.pop();
visit[now] = false;
for(i = 1; i <= n; i++)
{
if(dist[i] > dist[now] + map[now][i])
{
dist[i] = dist[now] + map[now][i];
if(visit[i] == false)
{
Q.push(i);
visit[i] = true;
}
}
}
}
}
int dfs(int now) //记忆化搜索
{
int i;
if(now == 2) return 1; //找到终点,返回1(1条路)
if(s[now]) return s[now]; //该点已经走过,返回:过该点有多少条路
for(i = 0; i < road[now].size(); i++)
{
if(dist[now] > dist[ road[now][i] ])
{
s[now] += dfs(road[now][i]);
}
}
return s[now]; //返回:该点一共可以有多少条路
}
int main()
{
while(scanf("%d", &n), n)
{
scanf("%d", &t);
init();
input();
spfa();
sum = dfs(1); //sum一共多少条路,sum = s[1] 也行
printf("%d\n", sum);
}
return 0;
}
分享到:
相关推荐
2. **高级算法**:包括动态规划(状态转移、记忆化搜索)、贪心策略、回溯法、分支限界法等。 3. **数据结构**:数组、链表、栈、队列、树(二叉树、平衡树如AVL和红黑树)、图(邻接矩阵、邻接表、最小生成树、...
《最短路问题详解》 在计算机科学领域,最短路问题是一个经典的图论问题,其目标是寻找网络中两点间路径的最小成本。这个问题在众多应用中都有所体现,如交通规划、通信网络设计、社交网络分析等。在本篇内容中,...
2. 图的遍历:深度优先搜索(DFS)、广度优先搜索(BFS)等。 * 题目1043:Eight,涉及到多种解决方法。 * 题目1044:Collect More Jewels,涉及到动态规划(DP)的概念。 3. 图的搜索:图的搜索算法、图的路径查找...
7. **记忆化搜索**:在动态规划或递归问题中,记忆化搜索是一种优化技术,它将已经计算过的结果存储起来,避免重复计算,从而提高效率。这种方法在解决复杂度较高的问题时非常有用,如斐波那契数列、最短路径问题等...
八数码的A*算法~不是很高效,但是很适合刚刚学这个算法的朋友们
5. **优化技巧**:如何减少时间复杂度,使用位运算优化、循环展开、记忆化搜索等方法提升代码效率。 6. **调试和测试**:理解如何编写测试用例来检查代码的正确性,以及如何利用调试工具定位和修复错误。 7. **...
- **变量声明与初始化**:例如 `int n, m, j, i, k, l;` 和 `long int a[1000];` 分别声明了多个整型变量和一个长度为1000的长整型数组。 - **循环结构**:使用 `for` 循环来实现重复操作,例如 `for(k=0;k;k++)` 和...
Problem Description 话说,经过了漫长的一个多月,小明已经成长了许多,所以他改了一个名字叫“大明”。 这时他已经不是那个只会做100以内加法的那个“小明”了,...请在一行里面输出输出A+B的值,请输出最简形式。
该代码主要采用了深度优先搜索(DFS)算法来解决问题。 #### 二、DFS(Depth First Search)算法原理 **定义:** DFS是一种用于遍历或搜索树或图的算法。在这个过程中,算法从根节点开始探索尽可能深的子节点路径...
8. **图论与树**:HDU题目中可能涉及图的遍历(深度优先搜索DFS、广度优先搜索BFS)、树的遍历(前序、中序、后序)以及最小生成树、最短路径等算法。 9. **动态规划**:这是一种优化策略,通过构建状态转移方程来...
HDU(杭州电子科技大学)在线评测系统是许多编程竞赛爱好者和学习者经常访问的平台,它提供了大量的算法题目供用户练习和挑战。这个压缩包文件“HDU 2000-2099 解题报告”显然包含了在这个题号范围内的一些问题、...
"hdu 1695 GCD(欧拉函数+容斥原理)" 题目大意是:给定 a, b, c, d, k,找到一队 x, y,满足 g(x, y) = k,且 x ∈ [1, b], y ∈ [1, d],问有多少对符合要求的 (x, y)。 思路是:gcd(x, y) == k 解释 x, y 都能...
搜索算法通常分为两类:盲目搜索(如BFS和DFS)和启发式搜索(如A*搜索)。 宽度优先搜索(BFS)是一种盲目搜索策略,它以“宽度”优先的方式遍历图或树。BFS从根节点开始,首先访问所有距离根节点一跳的节点,然后...
### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...
【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...
《杭电OnlineJudge 2000-2099解题报告》是针对杭州电子科技大学(HDU)在线评测系统(OnlineJudge)中2000至2099题目的详细解答集锦,主要涵盖了算法分析、编程技巧以及问题解决策略等内容。这份解题报告以CHM...
HDU 300+ AC 代码集合是一个包含超过300个已通过验证的算法解决方案的资源,这些代码主要用于解决各类计算机编程竞赛中的问题。这些竞赛通常由杭州电子科技大学(HDU)主办,旨在提升参赛者的算法设计、编程和问题...
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...