配点: 3 点
問題文
ABC田径俱乐部有 有 N 接力赛跑者。在接力赛中 1 玩家 1 我将负责一个病区。多个玩家 1 负责一个病区, 1 玩家不能负责多个区域。接力赛的赛道是 1 病房至 1 号 N 甚至还有守卫和玩家 i 是 j 跑完病房需要多长时间? A_{i, j} 。
接力传是第一个 1 区、第 2 区、……、第 N 负责该赛段的运动员按照所在区的顺序进行比赛。不。 j 区 (1 \leq j \leq N - 1) j + 1 您必须将腰带交给在病房跑步的运动员。此时,任务交接所需的时间已经足够短,可以忽略不计。最后获得腰带的玩家是第一个获得腰带的玩家 N 穿过病房并到达目标。
嗯,ABC 田径俱乐部有 有 M 谣言。i 第二个谣言是“玩家 X_i 和玩家 Y_i 关系并不好。” 据传参与其中的球员之间不可能交换腰带。换句话说,玩家 紧随 X_i 之后的玩家 Y_i 也是一位会跑步的运动员 Y_i 之后的玩家 X_i 甚至无法运行。
求 ABC 田径队在接力赛中到达目标所需的最短时间。然而,如果无论你如何决定每个运动员跑的路段都无法达到目标,那么 -1 ,否则输出
制約
- 1 \leq N \leq 10
- 1 \leq A_{i, j} \leq 1000 \ (1 \leq i \leq N, 1 \leq j \leq N)
- 0 \leq M \leq N(N - 1)/2
- 1 \leq X_i < Y_i \leq N \ (1 \leq i \leq M)
- (X_i, Y_i) \neq (X_j, Y_j) \ (i \neq j)
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N
A_{1, 1} A_{1, 2} \cdots A_{1, N}
A_{2, 1} A_{2, 2} \cdots A_{2, N}
\vdots
A_{N, 1} A_{N, 2} \cdots A_{N, N}
M
X_1 Y_1
X_2 Y_2
\vdots
X_M Y_M
出力
请输出达到目标所需的最短时间。然而,如果每个运动员无论如何确定跑的路段都无法达到目标, -1 ,否则输出
入力例 1
3 1 10 100 10 1 100 100 10 1 1 1 2
出力例 1
111
選手 1 是 1 病房跑步,运动员 2 是 3 病房跑步,运动员 3 是 2 在病房跑步的最小值 按顺序处理 111 可以实现。
入力例 2
4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 3 1 2 1 3 2 3
出力例 2
-1
入力例 3
3 1 10 100 10 1 100 100 10 1 0
出力例 3
3