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

    给定一张 \(n\) 个点的带权无向图,点从标号 \(0 \sim n-1\),求起点 $0$ 到终点 \(n-1\) 的最短$Hamilton$路径。 $Hamilton$路径的定义是从 $0$ 到 \(n-1\) 不重不漏地经过每个点恰好一次。

    输入格式

    第一行一个整数 \(n\)。 接下来 \(n\) 行每行 \(n\) 个整数,其中第 \(i\) 行第 \(j\) 个整数表示点i到j的距离(一个不超过的正整数,记为 \(a[i,j]\) )。 对于任意的 \(x,y,z\),数据保证 \(a[x,x]=0\)\(a[x,y]=a[y,x]\) 并且 \(a[x,y]+a[y,z] \geq a[x,z]\)

    $1 \leq n \leq 20$

    $0 \leq a[i, j] \leq 10^{7}$

    输出格式

    一个整数,表示最短Hamilton路径的长度。

    样例输入

    5
    0 2 4 5 1
    2 0 6 5 3
    4 6 0 8 3
    5 5 8 0 5
    1 3 3 5 0

    样例输出

    18

    提示

    从0到3的Hamilton路径有两条,0-1-2-3和0-2-1-3。前者的长度为2+2+1=5,后者的长度为1+2+1=4