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\)之间设置“休息处”。