TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P7156
  • 题目
  • P7156迷宫
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s,128m
    问题描述

    有一个迷宫,由 \(n*m\) 个房间构成,相邻两个房间的墙上都有门,每个房间都有一个数值,相邻两个房间的门只能从数值大的房间往数值小的房间推开,推门所耗体力为这两个房间数值最小者。 比如,相邻的 \(A,B\) 两个房间,对应的体力值分别为 $3$ 和 $5$ 。 那么,$A、B$间的门,只能从 \(B\)\(A\) 方向推开,需要耗费体力 $3$ 。
    一开始,迷宫里所有门都处于关闭状态,且所有房间都被抽空了空气。现在需要给迷宫灌入空气,充气阀在左上角第 $1$ 个房间,现在要你打开一些门,问,要使空气流到所有房间,最少需要花费多少力气去开门?

    输入格式

    第一行,两个整数 \(n\)\(m\) ,表示迷宫的行数和列数 ($3<=n,m<=100$)
    接下来一个 \(n*m\) 的整数矩阵,矩阵中的数字,表示对应房间的数值。数值在 $1 $到 $1000$ 以内。

    输出格式

    一个整数,表示所需最小总体力

    样例输入

    4 3
    3 5 2 1
    7 3 4 8
    1 6 5 7

    样例输出

    26