← 返回题目列表

AtCoder · typical90_af

032. AtCoder 接力赛

中文机器翻译题面 查看原题

配点: 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