← 返回题目列表

AtCoder · wupc2019_f

F. 角色扮演游戏

中文机器翻译题面 查看原题
F:角色扮演游戏

配点 : \(200\) 点

問題文

加藤君正在为某款RPG制作剧本。 在这个RPG中,有\(N\)个场景,每个场景都已经被确定为“战斗”或“林间空地”。 另外,还有连接\(M\)个场景的移动路径,第\(i\)条路径允许从场景\(a_i\)移动到场景\(b_i\)。 起初,RPG 的主角 Shinya-kun 位于场景 \(1\) 中,在通道中自由移动,并在到达场景 \(N\) 时完成游戏。

Shinya君有两种状态:“精力充沛”和“疲劳”。 你可以在“精力充沛”的状态下战斗,但你不能在“疲劳”的状态下战斗。 如果在“疲劳”状态下到达“战斗”场景,游戏就会结束。

Shinya-kun以“充满活力”的状态开始游戏。 经过一个“战斗”场景后,你会感到疲倦,进入“疲劳”状态。 为了从“疲劳”状态恢复到“活力”状态,必须经过一个“恢复站”。

“恢复站”可以放置在任何“空白区域”场景中。 在场景设置恢复站的成本 \(i \ (2 \leq i \leq N-1)\) 为 \(c_i\)。

目前,“康复中心”设立地点尚未确定。 因此,加藤君决定设立一个满足以下条件的“康复中心”。

  • 从场景\(1\)开始移动的慎也君,前往场景\(N\)无论你选择什么动作,从任何“战斗”场景到任何其他“战斗”场景时至少经过一次“治疗站”。
  • Shinya君通关后的状态可以是“疲劳”或“精力充沛”。

请求加藤君设立满足上述条件的“回收站”所需的最低总成本。 无论你如何设置“康复中心”,如果不能满足条件, -1 。 在

制約

  • \(3 \leq N \leq 500\)
  • \(N-1 \leq M \leq 1000\)
  • \(-1 \leq c_i \leq 10^9 \ (2 \leq i \leq N-1)\)
    • 如果\(c_i = -1\),则场景\(i\)是一个“战斗”场景。
    • 如果\(c_i \geq 0\),则场景\(i\)是一个“空地”场景,在那里设置“休息区”的成本为\(c_i\)。
  • \(1 \leq a_i , b_i \leq N \ (1 \leq i \leq M)\)
    • 表示有一个从场景\(a_i\)到场景\(b_i\)的通道。
  • 当将其视为由 \(N\) 个顶点 \(M\) 条边组成的有向图时,对于每个顶点,都有一条从顶点 \(1\) 到顶点 \(N\) 的路径。此外,没有闭合电路。
  • 所有输入值都是整数。

入力

输入是按以下格式从标准输入给出的。

\(N\) \(M\)
\(c_2\) \(c_3\) \(\dots\) \(c_{N-1}\)
\(a_1\) \(b_1\)
\(a_2\) \(b_2\)
\(\vdots\)
\(a_M\) \(b_M\)

出力

请输出满足条件的“恢复站”的最低总安装成本。 如果无法满足条件, -1 。 在


入力例 1

7 7
-1 100 10 1 -1
1 2
2 3
3 6
2 4
4 5
5 6
6 7

出力例 1

101

最佳选择是场景\(3\)和场景\(5\)。


入力例 2

4 3
-1 -1
1 2
2 3
3 4

出力例 2

-1

无法在场景\(2\)和场景\(3\)之间设置“休息处”。