AT_abc481_f.Evil Shortest Path
提高+/省选-
通过率:0%
时间限制:2.00s
内存限制:1024MB
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given a directed graph with N vertices and M edges. The vertices are numbered 1,2,…,N. The i-th edge goes from vertex Ai to vertex Bi, and a digit Ci between 1 and 9, inclusive, is written on this edge.
When moving along the edges in their directions, the integer obtained by concatenating the digits written on the traversed edges in the order they are traversed is called the score of the movement. For example, if the digits written on the traversed edges are 3,1,4 in this order, the score of the movement is 314. The same vertex or edge may be traversed multiple times.
For each v=2,3,…,N, find the minimum score of a movement from vertex 1 to vertex v, modulo 998244353. Here, it is guaranteed that the given directed graph allows moving from vertex 1 to every other vertex along the edges in their directions.
给你一个包含 N 个顶点和 M 条有向边的有向图。顶点编号为 1,2,…,N。第 i 条边从顶点 Ai 指向顶点 Bi,且该边上写有一个介于 1 到 9(含)之间的数字 Ci。
当沿着边的方向移动时,将所经过的各条边上所写的数字按经过顺序拼接而成的整数,称为该次移动的得分(score)。例如,若所经过的边上的数字依次为 3,1,4,则该次移动的得分为 314。同一顶点或同一条边可以被多次经过。
对每个 v=2,3,…,N,求从顶点 1 到顶点 v 的所有移动中,得分的最小值,并对 998244353 取模。题目保证:在给定的有向图中,一定存在一条从顶点 1 出发、沿边方向到达任意其他顶点的路径。
输入格式
The input is given from Standard Input in the following format:
N M
A1 B1 C1
A2 B2 C2
⋮
AM BM CM
输入从标准输入中按以下格式给出:
N M
A1 B1 C1
A2 B2 C2
⋮
AM BM CM
输出格式
Print N−1 lines. The (v−1)-th line should contain the value found for vertex v.
输出 N−1 行。第 (v−1) 行应包含顶点 v 对应的值。
输入输出样例
输入#1
4 4 1 2 1 1 3 1 2 4 9 3 4 2
输出#1
1 1 12
输入#2
3 5 1 2 9 1 2 2 2 2 1 1 3 9 2 3 1
输出#2
2 9
输入#3
11 11 1 2 9 2 3 9 3 4 8 4 5 2 5 6 4 6 7 4 7 8 3 8 9 5 9 10 3 9 10 2 10 11 9
输出#3
9 99 998 9982 99824 998244 9982443 99824435 998244352 998244352
说明/提示
Sample 1 Explanation:
- For vertex 2, 112 gives a score of 1.
- For vertex 3, 113 gives a score of 1.
- For vertex 4, 11294 gives a score of 19, and 11324 gives a score of 12, so the minimum is 12.
Thus, print 1,1,12, separated by newlines.
Sample 2 Explanation:
- For vertex 2, 192 gives a score of 9, and 122 gives a score of 2, so the minimum is 2.
- For vertex 3, 193 gives a score of 9, and 12213 gives a score of 21, so the minimum is 9.
Note that the given graph may contain multi-edges and self-loops.
Sample 3 Explanation:
Note that the score should be printed modulo 998244353.
Constraints
- 2≤N≤2×105
- N−1≤M≤2×105
- 1≤Ai,Bi≤N
- 1≤Ci≤9
- All input values are integers.
- It is possible to move from vertex 1 to every other vertex along the edges in their directions.
样例 1 解释:
- 对于顶点 2,路径 112 的得分为 1。
- 对于顶点 3,路径 113 的得分为 1。
- 对于顶点 4,路径 11294 的得分为 19,路径 11324 的得分为 12,因此最小得分为 12。
因此,按行输出 1、1、12。
样例 2 解释:
- 对于顶点 2,路径 192 的得分为 9,路径 122 的得分为 2,因此最小得分为 2。
- 对于顶点 3,路径 193 的得分为 9,路径 12213 的得分为 21,因此最小得分为 9。
注意:所给图中可能包含重边和自环。
样例 3 解释:
注意:得分需对 998244353 取模后输出。
约束条件
- 2≤N≤2×105
- N−1≤M≤2×105
- 1≤Ai,Bi≤N
- 1≤Ci≤9
- 所有输入值均为整数。
- 从顶点 1 出发,沿有向边可到达其余每个顶点。
输入解题思路,AI测评打分。不知道怎么写?