/ 21班 / 题库 /

偷拍硕哥1

偷拍硕哥1

测试数据来自 nnu_contest/5bfa795ed3d8a141466ee744

有一天,上帝来到人间。他见到的第一个人是出题人,发现出题人的智商奇低,十分伤心,于是决定毁灭世界。就在这危急关头,出题人突然说:“不,我只是人间最菜的。我知道一个人他智商通天,他叫硕哥。”于是,上帝让出题人去找他,并且拍一张照片给上帝,以证明是存在毛发浓密的顶级程序员的。但是,上帝的耐心并不好,所以你只有1s~10s帮助智障的出题人解决这个问题。
出题人目前在明理楼,你可以视为1号节点,目前时刻为0。
硕哥在宿舍,你可以视为n号节点。
出题人到硕哥的位置之间,有一些路口。这些路口之间有一些无向道路,出题人是个肥宅,他经过每条边要使用不同的时间。
但是,由于上帝的震怒,一些路口变得不稳定起来,所以很多路口在某个时间节点会崩塌,假设一个路口会在t时刻崩塌的话,那么怕死的智障出题人只能在任何一个小于t的时间点呆在这里。
现在给出道路关系图和每个节点崩塌的时间,求出题人到硕哥所在位置的最短时间,如果出题人无法找到硕哥,输出-1。
输入格式
第一行一个正整数n和一个正整数m,分别表示节点数和无向道路数目
第二行有用空格隔开的n个正整数,表示每个节点的崩塌时间
第三行到第m+2行 每行三个正整数a,b,c表示a节点到b节点之间有一条耗时为c的无向道路
ps:可能存在重边和自环
输出格式
输出一个整数 表示出题人到硕哥所在位置的最短时间,如果出题人无法找到硕哥,输出-1。

信息

ID
1010
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者

相关

在下列比赛中:

帅哥的比赛