{"problem":{"name":"[THUPC 2022 决赛] 倍增路径","description":{"content":"对于任意一张 DAG $G=(V,E)$ 和图中的一个起始点 $s_1\\in V$，倍增小游戏的规则为： - 在第 $i$ 轮操作（$i=1,2,\\cdots$）中，玩家选取一条起点为 $s_i$ 的**非空**路径 $p_i$，使得所有属于这条路径的边的边权和恰为 $(i+1)$ 的倍数。如果无法选择出满足倍数要求的路径，则称游戏失败，玩家将不会获得任何分数；否则，本轮操作成功，并记 $p_i","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8418"},"statements":[{"statement_type":"Markdown","content":"对于任意一张 DAG $G=(V,E)$ 和图中的一个起始点 $s_1\\in V$，倍增小游戏的规则为：\n\n- 在第 $i$ 轮操作（$i=1,2,\\cdots$）中，玩家选取一条起点为 $s_i$ 的**非空**路径 $p_i$，使得所有属于这条路径的边的边权和恰为 $(i+1)$ 的倍数。如果无法选择出满足倍数要求的路径，则称游戏失败，玩家将不会获得任何分数；否则，本轮操作成功，并记 $p_i$ 的终点为 $s_{i+1}$。\n\n- 在第 $i$ 轮操作成功后，玩家可以选择结束游戏或者继续第 $(i+1)$ 轮操作。如果选择结束游戏，则称选择出的 $i$ 条路径 $p_1, \\cdots, p_i$ 为倍增路径，并计算得分。\n\n如果游戏没有失败，则在结束游戏时，对于选出的倍增路径 $p_1, \\cdots, p_k$，定义游戏的分数为 $\\sum_{i=1}^k a_i \\left|p_i\\right|/k$，其中 $|p_i|$ 表示路径 $p_i$ 包含的边数，$a_i$ 是输入给定的权值。显然，无论如何选取路径，最多也只能选出 $(n-1)$ 条路径，因此输入中只给出了 $a_1, \\cdots, a_{n-1}$。\n\n为了设置每张图的通关要求，请对给出的 DAG 和起始点，计算该游戏的最大分数。\n\n## Input\n\n输入的第一行包含三个由空格隔开的正整数 $n$，$m$，$s_1$，表示给出的图中点的数量、边的数量及起始点的编号。保证 $2\\le n \\le 100$，$1\\le m\\le \\frac{n(n-1)}{2}$，$1\\le s_1\\le n$。\n\n输入的第二行包含 $(n-1)$ 个由空格隔开的正整数 $a_1, \\cdots, a_{n-1}$，表示计算分数时的权重。保证 $1\\le a_1\\le a_2\\le\\cdots\\le a_{n-1}\\le 10^9$。\n\n接下来 $m$ 行，每行输入三个由空格隔开的正整数 $u_i, v_i, w_i$，描述图中一条由 $u_i$ 连向 $v_i$，权值为 $w_i$ 的单向边。保证 $1\\le u_i, v_i\\le n$，$u_i\\ne v_i$，$1\\le w_i\\le 10^9$，图是连通的且没有重边。\n\n## Output\n\n输出仅一行，包括两个整数，由空格隔开。\n\n如果可以选出至少一条路径，则存在一种最优的选取方案使得分数最大，记这个最优分数的最简分数表示为 $p/q$（当最优分数恰为整数时认为 $q=1$），则输出 $p$，$q$。否则，如果无论如何选取都无法选取出至少一条路径，则输出 `-1 -1`。\n\n[samples]\n\n## Note\n\n【样例 1 解释】\n\n选出的倍增路径为 $p_1 = ((1, 2)), p_2 = ((2, 5))$。\n\n【数据范围与约定】\n\n对于 $100\\%$ 的数据，保证 $2\\le n\\le 100$，$1\\le m\\le \\frac{n(n-1)}{2}$，$1\\le s_1, u_i, v_i\\le n$，$1\\le a_1 \\le \\cdots\\le a_{n-1}\\le 10^9$，$1\\le w_i\\le 10^9$，输入的图是连通的且没有重边。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8418","tags":["2022","O2优化","THUPC"],"sample_group":[["5 5 1\n1 11 21 1211\n1 2 4\n1 3 11\n2 5 9\n3 4 12\n4 5 13\n","6 1\n"],["9 16 1\n1 10 100 1000 10000 100000 1000000 10000000\n1 2 2\n1 3 3\n2 3 5\n2 5 7\n3 4 11\n3 5 13\n3 6 17\n3 7 19\n4 7 23\n5 6 29\n5 8 31\n6 7 37\n6 8 41\n6 9 43\n7 9 47\n8 9 53\n","221 3\n"]],"created_at":"2026-03-03 11:09:25"}}