题目描述
对于任意一张 DAG G=(V,E) 和图中的一个起始点 s1∈V,倍增小游戏的规则为:
- 在第 i 轮操作(i=1,2,⋯)中,玩家选取一条起点为 si 的非空路径 pi,使得所有属于这条路径的边的边权和恰为 (i+1) 的倍数。如果无法选择出满足倍数要求的路径,则称游戏失败,玩家将不会获得任何分数;否则,本轮操作成功,并记 pi 的终点为 si+1。
- 在第 i 轮操作成功后,玩家可以选择结束游戏或者继续第 (i+1) 轮操作。如果选择结束游戏,则称选择出的 i 条路径 p1,⋯,pi 为倍增路径,并计算得分。
如果游戏没有失败,则在结束游戏时,对于选出的倍增路径 p1,⋯,pk,定义游戏的分数为 ∑ki=1ai|pi|/k,其中 |pi| 表示路径 pi 包含的边数,ai 是输入给定的权值。显然,无论如何选取路径,最多也只能选出 (n−1) 条路径,因此输入中只给出了 a1,⋯,an−1。
为了设置每张图的通关要求,请对给出的 DAG 和起始点,计算该游戏的最大分数。
输入格式
输入的第一行包含三个由空格隔开的正整数 n,m,s1,表示给出的图中点的数量、边的数量及起始点的编号。保证 2≤n≤100,1≤m≤n(n−1)2,1≤s1≤n。
输入的第二行包含 (n−1) 个由空格隔开的正整数 a1,⋯,an−1,表示计算分数时的权重。保证 1≤a1≤a2≤⋯≤an−1≤109。
接下来 m 行,每行输入三个由空格隔开的正整数 ui,vi,wi,描述图中一条由 ui 连向 vi,权值为 wi 的单向边。保证 1≤ui,vi≤n,ui≠vi,1≤wi≤109,图是连通的且没有重边。
输出格式
输出仅一行,包括两个整数,由空格隔开。
如果可以选出至少一条路径,则存在一种最优的选取方案使得分数最大,记这个最优分数的最简分数表示为 p/q(当最优分数恰为整数时认为 q=1),则输出 p,q。否则,如果无论如何选取都无法选取出至少一条路径,则输出 -1 -1
。
样例数据
样例 1 输入
5 5 1
1 11 21 1211
1 2 4
1 3 11
2 5 9
3 4 12
4 5 13
样例 1 输出
6 1
样例 1 解释
选出的倍增路径为 p1=((1,2)),p2=((2,5))。
样例 2 输入
9 16 1
1 10 100 1000 10000 100000 1000000 10000000
1 2 2
1 3 3
2 3 5
2 5 7
3 4 11
3 5 13
3 6 17
3 7 19
4 7 23
5 6 29
5 8 31
6 7 37
6 8 41
6 9 43
7 9 47
8 9 53
样例 2 输出
221 3
子任务
对于 100% 的数据,保证 2≤n≤100,1≤m≤n(n−1)2,1≤s1,ui,vi≤n,1≤a1≤⋯≤an−1≤109,1≤wi≤109,输入的图是连通的且没有重边。