seuOJ317 - 小塔

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：2000 ms
• 空间限制：256 MiB
• 题目标签：冬季, 校赛, 初赛, 2020

题目描述

小塔是东南大学渣男界永远的传说。

靠着一头飘逸的金色秀发，小塔能俘获所有女生的芳心。有传闻说他曾经同时和五十个女生交往，有传闻说他可以在三分钟内让素昧平生的女生爱上他，还有传闻说他可以做到男女通吃……

有多少谣传是真的呢？谁也不知道。但总之，小塔有复数个女朋友这一点似乎是确凿无疑的。

让我们把视角转到小塔身上。现在，他有 $n$ 个女朋友，每个人都住在东南大学不同的地方。每个女朋友的住址可以视为一个点，一共有 $n$ 个点。在点之间，存在着双向的道路连接着不同的两个点，经过每条道路视长度和路况都要消耗一定的时间。整个东南大学可以被视为 $n$ 个点的无向带权连通图。

在每个晚上，小塔都要去见他所有女朋友一面，以巩固他们之间的关系。具体来说，他可以选择任意一个 $1$ 到 $n$ 的排列 $a_1,a_2,a_3……a_n$ ，从点 $a_1$ 开始，依次到达 $a_2$，$a_3$ 直至 $a_n$ 。在序列上经过连续的两个点时，小塔可以借道别的点来缩短路途上的时间消耗。到达 $a_1$ 所需的时间不需要纳入计算。

但是，作为东南大学的学生，小塔的女朋友们也是要学习的。对于每个女朋友 $i$ 和序列中的每个位置 $j$，都有一个bool值 $f_{i,j}$ 来表示 $i$ 号女朋友 $j$ 时刻的在寝状态。如果 $f_{i,j}$ 为 $0$，就代表小塔选择第 $j$ 个拜访女生 $i$ 时，女生会因为去图书馆学习而不在寝室。扑空的小塔会不知所措地呆立在原地，很容易被宿舍其他的人发现。如此，小塔的渣男名声就会散开，这对于小塔是无法接受的。所以，对于上述的序列 ${a_i}$，必须保证对于所有 $i$ ，$f_{a_i,i}=1$ 都成立。

现在，小塔想知道，如果合理地安排拜访的序列，他每晚最少需要多少时间才能拜访完所有的女生？我们假设小塔的渣男技巧出神入化，和每个女朋友的见面时间可以被视为 $0$ 。

输入格式

输入第一行是一个正整数$n$（ $1 \leq n \leq 18$），代表了小塔女朋友的数目。

接下来的 $n$ 行，每行有 $n$ 个非负整数，构成一个矩阵。第 $i$ 行第 $j$ 个元素 $d_{i,j}$（ $0 \leq d_{i,j} \leq 1000$ ）代表了小塔的 $i$ 号女朋友和 $j$ 号女朋友宿舍之间的直接道路的距离。如果该值为 $0$ ，代表宿舍之间无直接道路。数据保证 $d_{i,j}=d_{j,i}$ 恒成立。

再下面 $n$ 行，每行一个长度为 $n$ 的01串 $f_i$，代表了小塔 $i$ 号女朋友的在寝状态，含义如题目描述。

数据保证宿舍间互相连通，不存在自环，且存在拜访的序列使得可以拜访 $n$ 位女朋友时她们都在寝。

输出格式

一行一个正整数，代表了小塔最少需要的时间。

样例

样例输入

3
0 1 3
1 0 2
3 2 0
111
111
111

样例输出

3

数据范围与提示

【后记】

我们不知道小塔是什么时候从世人的视线中消失的，就像我们不知道明天和意外哪个先来。

是夜，无月无风夜微明。

小塔走在前往他最后一个女朋友宿舍的路上，昏黄的路灯下，他却看到另一个熟悉的身影。

是他今晚第一个见到的女朋友。

可是，熟悉的身影旁边，是另一个陌生的高大身影。他们的头靠得很近，脸上洋溢着幸福的笑容。

“怎么会……”小塔呆立着喃喃，不觉已泪流满面。

渣人者，人恒渣之，这是人类社会的铁律。

可是，小塔身为渣男的高傲自尊，不允许他被渣女玩弄感情。

他回头，抹掉眼泪，大跨步着奔向远方，奔向渺远的地平线。

从此以后，东南大学里再也没有了“小塔”这个身份，只剩下一个都市传说和一个逡巡在大鸟转转转酒吧的身影。