题目描述: 虽然已经上了两年大学,但是王大山同学仍然无法记住每门课上课的教室(也可能是因为课实在是太多了),导致经常走错教室,或者是无法找到从当前教室到目标教室的最短路程。现在王大山同学交给你一个光荣且艰巨的任务,请你编写一个程序,帮助他找到从当前教室到目标教室的最短路程(请好好写,你也不想让大山上课迟到对吧? :) )。 输入格式: 第一行给出一个值n。 接下来的n行,给出三个值,中间以空格隔开,分别是教室a,教室b,和教室a与教室b之间的距离。 最后一行给出两个值,中间以空格隔开,分别是王大山当前所在教室和王大山的目标教室。 输出格式: 输出一个值,表示王大山从当前教室到目标教室的最短路程。 输入样例: 在这里给出一组输入。例如: 5 1 2 10 1 3 1 2 5 4 3 4 2 4 5 3 1 5 输出样例: 在这里给出相应的输出。例如: 6 代码长度限制 100 KB 时间限制 400 ms 内存限制 512 MB
时间: 2024-04-02 14:35:04 浏览: 10
这道题目是一个典型的最短路径问题,可以使用Dijkstra算法来解决。
Dijkstra算法的基本思路是从起点开始,先初始化所有节点到起点的距离为无穷大,然后将起点到自己的距离设为0。接着,每次选择一个未标记的离起点最近的节点,并标记它。然后根据这个节点,更新其它节点到起点的距离。重复这个过程,直到找到目标节点或者所有节点都被标记。
下面给出代码实现:
相关问题
PHPExcel_Cell_DataType::TYPE_FORMULA 代码是什么?
PHPExcel_Cell_DataType::TYPE_FORMULA 是一个常量,它表示 Excel 单元格中的数据类型为公式。这个常量被用于 PHPExcel 的编程中,用以处理 Excel 文件的数据。
drizzle 前往山地统计大山的数目,现在收到这片区域的地图,地图中用0(平地)和1(山峰)绘制而成,请你帮忙计算其中的大山数目 山总是被平地四面包围着,每一座山只能在水平或垂直方向上连接相邻的山峰而形成。一座山峰四面被平地包围,这个山峰也算一个大山 另外,你可以假设地图的四面都被平地包围着。
根据文中所述,现在所在的区域地图中,平地和山峰分别被绘制成0(平地)和1(山峰)的形式。需要计算其中的大山数目。由于每座山峰四面被平地包围,每一座山峰只能在水平或垂直方向上连接相邻的山峰而形成。每一座山峰四面都被平地包围,那么这个山峰也算是一个大山。另外,你可以假设地图的四面都被平地包围。