这是 a960 DESTRUCTION 3,2,1 的困难版本。
O Fortuna velut luna statu variabilis
772 A.P. 08.01 幽蓝边界到达月面
幽蓝边界到达律动星后便直向月面而去。Gino和鸠相约在海滩等待最后的时刻。
月面基地共有n个被由1到n编号的模块。其中有些模块被双向异想传送门两两连接，但是通过传送门需要时间wi。
Gino现在位于x号模块，鸠位于y号模块。他们要使用传送门前往n号模块——海滩所在之地。
但是幽蓝边界在持续吞噬着像素塔，留给Gino和鸠的时间不多了，i号模块将会在时刻ti被吞噬。
幸好，碎数研在海滩上点放了黄绿色的烟花，改变了PhigrOS被统治局按计划毁灭的命运。每个烟花可以把在PhigrOS中不幸落入幽蓝边界的人的数据修复一次。这使得Gino和鸠可以走进被幽蓝边界吞噬的基地，然后被烟花修复数据，再利用异想传送门传送到下一个基地。
但是碍于统治局的压力，碎数研只点放了k个黄绿色的烟花。这意味着Gino和鸠最多可以途经已被幽蓝边界吞噬的基地共k次。
命运有了转折后，Gino和鸠还能安全地到达n号模块吗？
第一行包含一个整数 T —— 测资的个数
对于每组测资：
第一行包含三个用空格分开的整数：n, m, k —— 月面基地模块数量、异想传送门的数量和烟花的数量
第二行包含两个用空格分开的整数：x, y —— Gino和鸠所在的月面基地模块编号
第三行包含n个用空格分开的整数：ti —— 月面基地被吞噬的时间
随后m行分别包括三个整数：ui, vi, wi —— 表示基地ui和vi有传送门连接，需要wi时间通过
对于每组测资输出一行
第一行包括用空格分开的两个数：Gino和鸠到达月面基地n需要的时间
如有多组答案，先最小化较迟到达的人需要用的时间，再最小化较早到达的人需要用的时间
如果一个人不能安全到达月面基地n，则他到达月面基地n的时间为-1
1 8 9 1 4 7 6 10 6 2 11 1 1 100 1 4 5 1 3 1 1 2 3 2 3 9 3 6 10 3 5 2 5 8 4 6 8 3 6 7 2
-1 5
不公開 測資點#0 (10%): 10.0s , <50M
不公開 測資點#1 (10%): 10.0s , <50M
不公開 測資點#2 (10%): 10.0s , <50M
不公開 測資點#3 (10%): 10.0s , <50M
不公開 測資點#4 (10%): 10.0s , <50M
不公開 測資點#5 (10%): 10.0s , <50M
不公開 測資點#6 (10%): 10.0s , <50M
不公開 測資點#7 (10%): 10.0s , <50M
不公開 測資點#8 (10%): 10.0s , <50M
不公開 測資點#9 (10%): 10.0s , <50M
1 ≤ T ≤ 10
1 ≤ n, m ≤ 105
1 ≤ x, y ≤ n
0 ≤ k ≤ 30
ti ≤ 109
sum(w) ≤ 109
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||