QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB
[0]

# 4319. 倍增路径

Statistics

题目描述

对于任意一张 DAG G=(V,E) 和图中的一个起始点 s1V,倍增小游戏的规则为:

  • 在第 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 是输入给定的权值。显然,无论如何选取路径,最多也只能选出 (n1) 条路径,因此输入中只给出了 a1,,an1

为了设置每张图的通关要求,请对给出的 DAG 和起始点,计算该游戏的最大分数。

输入格式

输入的第一行包含三个由空格隔开的正整数 nms1,表示给出的图中点的数量、边的数量及起始点的编号。保证 2n1001mn(n1)21s1n

输入的第二行包含 (n1) 个由空格隔开的正整数 a1,,an1,表示计算分数时的权重。保证 1a1a2an1109

接下来 m 行,每行输入三个由空格隔开的正整数 ui,vi,wi,描述图中一条由 ui 连向 vi,权值为 wi 的单向边。保证 1ui,vinuivi1wi109,图是连通的且没有重边。

输出格式

输出仅一行,包括两个整数,由空格隔开。

如果可以选出至少一条路径,则存在一种最优的选取方案使得分数最大,记这个最优分数的最简分数表示为 p/q(当最优分数恰为整数时认为 q=1),则输出 pq。否则,如果无论如何选取都无法选取出至少一条路径,则输出 -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% 的数据,保证 2n1001mn(n1)21s1,ui,vin1a1an11091wi109,输入的图是连通的且没有重边。