TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1016
  • 题目
  • P1016小胖办证
    限制 : 时间限制 : 1000 MS   空间限制 : 65536 KB
    问题描述

    xuzhenyi要办个签证。办证处是一座M层的大楼,1<=M<=100。每层楼都有N个办公室,编号为1..N(1<=N<=500)。每个办公室有一个签证员。签证需要让第M层的某个签证员盖章才有效。每个签证员都要满足下面三个条件之一才会给xuzhenyi盖章:
    1. 这个签证员在1楼
    2. xuzhenyi的签证已经给这个签证员的正楼下(房间号相同)的签证员盖过章了。
    3. xuzhenyi的签证已经给这个签证员的相邻房间(房间号相差1,楼层相同)的签证员盖过章了。
    每个签证员盖章都要收取一定费用,总费用不超过1000000000。找出费用最小的盖章路线,使签证生效

    输入格式

    第1行两个整数M和N。
    接下来M行每行N个整数,第i行第j个数表示第i层的第j个签证员收取的费用。

    输出格式

    一个数。最小费用。

    样例输入 1

    3 4
    10 10 1 10
    2 2 2 10
    1 10 10 10

    样例输出 1

    8

    样例输入 2

    5 5
    1 1 1 3 1
    10 10 10 1 10
    1 1 1 1 1
    10 1 10 10 10
    5 6 7 8 9

    样例输出 2

    14