/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
Copyright (c) 2011 panyanyany All rights reserved.
URL : http://acm.hdu.edu.cn/showproblem.php?pid=1142
Name : 1142 A Walk Through the Forest
Date : Friday, January 13, 2012
Time Stage : 4 hours
Result:
5252336 2012-01-13 16:18:59 Accepted 1142
78MS 4124K 2027 B
C++ pyy
5252323 2012-01-13 16:16:15 Wrong Answer 1142
62MS 4124K 2046 B
C++ pyy
Test Data :
Review :
一开始果断不会做,但想靠自己的大脑想出答案来……结果思索了几个小时
死了无数脑细胞,终于还是想不出来,只能看答案了……
解题思路果然是相当有技巧啊……
下面是几位大牛们的解题报告:
http://www.cnblogs.com/liuqidong/archive/2010/07/28/1787217.html
http://www.cppblog.com/Dreams/archive/2010/09/04/78871.html
很好很强大,只是我觉得这种做法好像不能处理
下面的数据:
5 6
1 3 3
1 4 2
3 4 1
1 5 12
4 2 34
5 2 24
正确结果为 2
可惜我的思路又不正确= =!
我觉得这题好奇怪啊~~纠结啊
//----------------------------------------------------------------------------*/
#include <stdio.h>
#include <string.h>
#define min(x, y) ((x) < (y) ? (x) : (y))
#define max(x, y) ((x) > (y) ? (x) : (y))
#define INF 0x3f3f3f3f
#define MAXN 1002
bool used[MAXN] ;
int n, m ;
int map[MAXN][MAXN], dist[MAXN], pathCnt[MAXN] ;
// 由 dijkstra 算出各点到 home 的距离
void dijkstra ()
{
int i, j ;
int iMinPath, MinPath ;
memset (used, 0, sizeof (used)) ;
for (i = 1 ; i <= n ; ++i)
dist[i] = map[2][i] ;
dist[2] = 0 ;
for (i = 1 ; i <= n ; ++i)
{
iMinPath = 0 ;
MinPath = INF ;
for (j = 1 ; j <= n ; ++j)
if (!used[j] && dist[j] < MinPath)
{
iMinPath = j ;
MinPath = dist[j] ;
}
used[iMinPath] = true ;
for (j = 1 ; j <= n ; ++j)
{
if (!used[j])
dist[j] = min (dist[iMinPath] + map[iMinPath][j], dist[j]) ;
}
}
}
// 用 dfs 计算一共有多少条 最短路
int dfs (const int start)
{
if (start == 2)
return 1 ;
// 若 start 点已被检查过,则直接返回
if (pathCnt[start] != -1)
return pathCnt[start] ;
int i, sum ;
sum = 0 ;
for (i = 1 ; i <= n ; ++i)
{
// start 和 i 之间必须有直接路径,
// 且此路径加上 i 到 home 的距离 等于 start 到 home 的距离
/*
dist[start] > dist[i] 这种写法我觉得应该是不对的,因为它过不了下面的数
据:
5 6
1 3 3
1 4 2
3 4 1
1 5 12
4 2 34
5 2 24
正确答案为 2 (如果我没有算错的话)
换成这样子就可以过:
(map[start][i] == dist[start] - dist[i]))
但是却过不了杭电……
*/
if ((map[start][i] != INF) && dist[start] > dist[i])
{
sum += dfs (i) ;
}
}
return pathCnt[start] = sum ;
}
int main ()
{
int i ;
int x, y, c ;
while (scanf ("%d", &n), n)
{
scanf ("%d", &m) ;
memset (map, INF, sizeof (map)) ;
for (i = 0 ; i < m ; ++i)
{
scanf ("%d%d%d", &x, &y, &c) ;
map[x][y] = map[y][x] = c ;
}
dijkstra () ;
memset (pathCnt, -1, sizeof (pathCnt)) ;
printf ("%d\n", dfs(1)) ;
}
return 0 ;
}
分享到:
相关推荐
《杭电HDU ACM培训课件》是一份珍贵的学习资源,源自杭州电子科技大学的ACM竞赛培训课程。这些课件是官方论坛上分享的,旨在为那些积分不足无法获取资源或者对ACM编程竞赛感兴趣的初学者提供帮助。下面将详细阐述这...
多种路径规划算法c++实现源码+运行说明(dijkstra+RRT算法+A星算法+DWA) 【项目简介】 dijkstra算法中有bfs,dfs的实现,RunCode即可 RRT算法可视化采用opencv实现 DWA算法可视化采用matplotlib-cpp实现,配置文件的...
在这个项目中,"标准C的图的实现+BFS和DFS遍历+Dijkstra算法+Prim算法+Kruskal算法实现"涵盖了图的多种核心操作和算法。接下来,我们将详细讨论这些知识点。 首先,我们来看图的实现。在标准C语言中,图可以使用...
### 图论Dijkstra最短路径算法MATLAB程序详解 #### 一、算法背景与原理介绍 **Dijkstra算法**是一种用于解决带权图中的单源最短路径问题的经典算法。该算法由荷兰计算机科学家Edsger W. Dijkstra于1956年提出,并...
代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法...
Dijkstra算法最简单的实现方法是用一个链表或者数组来存储所有顶点的集合Q,所以搜索Q中最小元素的运算(Extract-Min(Q))只需要线性搜索Q中的所有元素。这样的话算法的运行时间是O(n2)。
最短路问题__Dijkstra(迪杰斯特拉算法).ppt
在实际应用中,为了提高效率,可以使用优化的Dijkstra算法,例如A*搜索算法,它结合了Dijkstra的贪婪特性与启发式信息,能够更快地找到目标节点。此外,对于大规模图,可以使用分布式或并行版本的Dijkstra算法来分摊...
最短路Dijkstra算法 Matlab代码Function部分,通用各种类型网络
这里提到的最短路算法是迪杰斯特拉算法(Dijkstra's Algorithm)。迪杰斯特拉算法是一种解决单源最短路径问题的算法,适用于加权无环图或非负权重的有向图。在给定的题目中,我们需要找到A城市到其他所有城市的最短...
毕设项目:基于springboot+mysql+Dijkstra算法实现物流优化管理系统.zip主要针对计算机相关专业的正在做课程设计和期末大作业的学生和需要项目实战练习的学习者。包含全部项目源码、该项目可以直接使用、项目都经过...
Dijkstra最短路算法是一种经典的图论算法,用于在加权有向图或无向图中寻找从指定起点到其余所有节点的最短路径。该算法由荷兰计算机科学家艾兹格·迪科斯彻(Edsger W. Dijkstra)于1956年提出,以他的名字命名。其...
Dijkstra最短路径算法是一种经典的图论算法,用于在加权有向或无向图中找到从源节点到其余所有节点的最短路径。这个算法由荷兰计算机科学家艾兹格·迪科斯彻(Edsger W. Dijkstra)于1956年提出,被广泛应用于网络...
迪杰斯特拉(Dijkstra)算法是一种用于解决单源最短路径问题的图算法,由荷兰计算机科学家艾兹格·迪杰斯特拉在1956年提出。它能够找到从一个特定源节点到图中所有其他节点的最短路径。在C++中实现这个算法,我们...
### Dijkstra算法——求解最短路径问题 #### 概述 Dijkstra算法是一种用于解决图论中最短路径问题的经典算法。它能够有效地找到两点之间的最短路径,并且被广泛应用于计算机科学、地理信息系统(GIS)、网络路由...
狄克斯特拉(Dijkstra)算法是一种用于解决单源最短路径问题的算法,由荷兰计算机科学家艾兹格·狄克斯特拉在1959年提出。在图论中,给定一个带权重的有向图,狄克斯特拉算法能够找出从源节点(source)到其他所有...
在计算机科学领域,路径搜索和图论算法是解决复杂网络问题的关键工具,其中"最短路算法"尤为重要。本文将详细探讨两种著名的最短路径算法:Dijkstra算法和A*算法,以及它们在实际问题中的应用。 Dijkstra算法,由...
dijkstraC++ dijkstra算法 dijkstra算法 dijkstra算法 dijkstra算法 dijkstra算法