#P1171. 售货员的难题

售货员的难题

题目背景

数据有更改

题目描述

某乡有 nn 个村庄,有一个售货员,他要到各个村庄去售货,各村庄之间的路程 si,js_{i,j} 是已知的,且 AA 村到 BB 村与 BB 村到 AA 村的路大多不同。为了提高效率,他从商店出发到每个村庄一次,然后返回商店所在的村,假设商店所在的村庄为 11,他不知道选择什么样的路线才能使所走的路程最短。请你帮他选择一条最短的路。

输入格式

第一行是一个整数,表示村庄数 nn
接下来 nn 行,每行 nn 个整数,第 ii 行的第 jj 个整数表示 iijj 的单向路径的距离 si,js_{i,j}

输出格式

一行一个整数表示最短的路程。

3
0 2 1
1 0 2
2 1 0
3

提示

对全部的测试数据,保证 2n202 \leq n \leq 201si,j<1031 \leq s_{i,j} < 10^3