lzh 的成仙之路
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
大家都玩过一个游戏叫《成仙之路》
在这个游戏中，玩家需要经过不断的和其他人交易或者合成物品，最终获得能够让自己成仙的道具
现在 lzh 为了比别人更快的通关游戏，于是她准备给自己开个金手指
假设现在总共有 $n$ 个 NPC，每个人手里有一种物品，第 $i$ 个人手里的物品编号为 $i$
现在 lzh 的目标是获得 $1$ 号物品，来使得自己成仙
游戏过程中，玩家有两种方式可以获得物品
1. 直接问物品持有人买，购买一件第 $i$ 种物品需要花费 $v_i$ 的金钱
2. 尝试用两件道具合成一件新的物品，游戏中共有 $m$ 条不同的合成公式
lzh 可以在游戏开始时利用金手指修改自己原本为 $0$ 的金钱，但是她又不想作弊的太明显
所以她想知道，她最少给自己多少初始金钱，可以使得自己经过不断操作获得 $1$ 号物品？
输入格式
输入第一行包含两个整数 $n,m$，表示有 $n$ 个人和 $m$ 条合成公式
第二行有 $n$ 个整数，分别为 $v_1,v_2,v_3...$ 分别表示每个物品的价格
接下来 $m$ 行，每行包含三个整数 $x_i,y_i,z_i$ 表示一条合成公式，含义为 $x$ 号物品可以由 $y$ 物品加 $z$ 号物品合成得到
对于 $40\%$ 的数据：$1 \leq n,m \leq 100$
对于 $100\%$ 的数据：$1 \leq n \leq 10^4, 1 \leq m \leq 10^5, 1 \leq v_i \leq 10^9$
输入保证$(1 \leq x_i,y_i,z_i \leq n, x_i \not{=} y_i \not {=} z_i)$
输出格式
输出一个整数表示最少的初始金钱
样例
5 3
5 0 1 2 5
5 2 3
4 2 3
1 4 522024提高组模拟赛(1)
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 3
- 开始于
- 2024-3-16 21:00
- 结束于
- 2024-3-26 21:00
- 持续时间
- 240 小时
- 主持人
-
huangzhe
- 参赛人数
- 20
