TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3783
  • 题目
  • P3783迷宫
    限制 : 时间限制 : - MS   空间限制 : 165536 KB
    评测说明 : 1000ms
    问题描述

    ZMY跑在打架的路上 ,跋山涉水。他突然发现自己走进了一个正方形迷宫,迷宫周围是险峻的高山和ZMY打不动的高山和打得动却走不过去的高山,所以他只能从迷宫中通过。这时天空突然一阵惊雷劈过,一个静坐沉思改悔的灵魂出现,他对ZMY说:现在我给你这座迷宫的地图,迷宫上每条边的权值都被标在了上面。现在给你机会增大某些边的权值,你要使得从迷宫左上角到右下角的每一条路径的长度都相等。当然你只能向右或向下走。只有这样,我才让你走出这座迷宫,继续你的打架旅程。

    ZMY要从左上角走到右下角

    ZMY为了能尽快走出迷宫,想让增加权值之后所有路径的相等的长度尽量小,你能帮帮他吗?

    输入格式

    第一行一个整数 N,表示正方形迷宫的边长

    接下来N行,每行N-1个整数,第i行第j个数表示迷宫中第i行从左到右第j条边的边权

    接下来N行,每行N-1个整数,第i行第j个数表示迷宫中第i列从上到下第j条边的边权

    输出格式

    一行,一个整数,表示ZMY在满足所有路径长度相等的情况下可以获得的最小路径长度。

    样例输入

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

    样例输出

    25

    提示

    20%的数据保证 N <= 5

    40%的数据保证 N <= 100

    100%的数据保证N <= 600, 1 <= 边权 <= 500

    ZMY修改的路径已在图中用红色标出,可以看出,路径中每一条只向右或向下走的路径的长度均相等且总长度25最小


    来源  zmy