首页 > 其他 > 详细

2019/11/2模拟赛&&OJ

时间:2019-11-02 21:12:32      阅读:78      评论:0      收藏:0      [点我收藏+]

T1:【题目描述】
cwbc 来到一个迷宫中, 这个迷宫是一个 n 行 m 列的网格, 起点在第 sx 行第
sy 列, 终点在第 tx 行第 ty 列。 迷宫里的每个格子上有一个数字, 第 i 行第 j
列的数字记为 a(i,j)。
cwbc 从起点开始, 每次可以跳到同一行或者同一列的某个格子, 但是这一
跳会产生一定的花费, 花费的大小为起跳点和落地点之间所有格子(包含这两个
格子) 上的数字的最小值。
cwbc 看这些数字看得头晕眼花, 只能来找你求助, 请你求出从起点到终点
的最小总花费。
【输入格式】
第一行六个正整数 n,m,sx,sy,tx,ty, 即题目描述中的含义。
接下来 n 行, 每行 m 个正整数, 描述这个迷宫, 第 i 行第 j 列的数字即为
a(i,j)。
【输出格式】
一行, 一个正整数表示从起点到终点的最小总花费。
【样例输入】
5 4 3 1 4 3
3 4 4 1
8 6 1 6
8 7 7 7
9 8 7 6
【样例输出】
6
【样例解释】
行走路线为(3,1)→(1,1)→(1,4)→(1,3)→(4,3)。
总花费为 3+1+1+1=6。
【数据规模和限制】
对于全部测试数据, 保证 1<=n*m<=100,000, 1<=a(i,j)<=1,000。
保证起点与终点不同。
各个测试点的数据规模及特性如下表。

测试点 n,m 特性
1 <=3
2 <=2000 所有 a(i,j)相等
3 <=70
4



5 <=150
6
7 <=8000
8
9
10

 



我们考虑处理这些点的关系:

思路:建图+dij

考虑给这些二维坐标节点进行标号,对所有同一行同一列的点进行建边:

边权为这些节点之间的最小值!

然后在起点和终点之间进行dij就可以了

 

2019/11/2模拟赛&&OJ

原文:https://www.cnblogs.com/little-cute-hjr/p/11783783.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!