AT_abc481_f.Evil Shortest Path

提高+/省选-

通过率:0%

时间限制:2.00s

内存限制:1024MB

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

You are given a directed graph with NN vertices and MM edges. The vertices are numbered 1,2,…,N1,2,\ldots,N. The ii-th edge goes from vertex AiA_i to vertex BiB_i, and a digit CiC_i between 11 and 99, 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,43,1,4 in this order, the score of the movement is 314314. The same vertex or edge may be traversed multiple times.

For each v=2,3,…,Nv=2,3,\ldots,N, find the minimum score of a movement from vertex 11 to vertex vv, modulo 998244353998244353. Here, it is guaranteed that the given directed graph allows moving from vertex 11 to every other vertex along the edges in their directions.

给你一个包含 NN 个顶点和 MM 条有向边的有向图。顶点编号为 1,2,…,N1,2,\ldots,N。第 ii 条边从顶点 AiA_i 指向顶点 BiB_i,且该边上写有一个介于 11 到 99(含)之间的数字 CiC_i。

当沿着边的方向移动时,将所经过的各条边上所写的数字按经过顺序拼接而成的整数,称为该次移动的得分(score)。例如,若所经过的边上的数字依次为 3,1,43,1,4,则该次移动的得分为 314314。同一顶点或同一条边可以被多次经过。

对每个 v=2,3,…,Nv=2,3,\ldots,N,求从顶点 11 到顶点 vv 的所有移动中,得分的最小值,并对 998244353998244353 取模。题目保证:在给定的有向图中,一定存在一条从顶点 11 出发、沿边方向到达任意其他顶点的路径。

输入格式

The input is given from Standard Input in the following format:

NN MM
A1A_1 B1B_1 C1C_1
A2A_2 B2B_2 C2C_2
⋮\vdots
AMA_M BMB_M CMC_M

输入从标准输入中按以下格式给出:

NN MM
A1A_1 B1B_1 C1C_1
A2A_2 B2B_2 C2C_2
⋮\vdots
AMA_M BMB_M CMC_M

输出格式

Print N−1N-1 lines. The (v−1)(v-1)-th line should contain the value found for vertex vv.

输出 N−1N-1 行。第 (v−1)(v-1) 行应包含顶点 vv 对应的值。

输入输出样例

  • 输入#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 22, 1→121\xrightarrow{1}2 gives a score of 11.
  • For vertex 33, 1→131\xrightarrow{1}3 gives a score of 11.
  • For vertex 44, 1→12→941\xrightarrow{1}2\xrightarrow{9}4 gives a score of 1919, and 1→13→241\xrightarrow{1}3\xrightarrow{2}4 gives a score of 1212, so the minimum is 1212.

Thus, print 1,1,121, 1, 12, separated by newlines.

Sample 2 Explanation:

  • For vertex 22, 1→921\xrightarrow{9}2 gives a score of 99, and 1→221\xrightarrow{2}2 gives a score of 22, so the minimum is 22.
  • For vertex 33, 1→931\xrightarrow{9}3 gives a score of 99, and 1→22→131\xrightarrow{2}2\xrightarrow{1}3 gives a score of 2121, so the minimum is 99.

Note that the given graph may contain multi-edges and self-loops.

Sample 3 Explanation:
Note that the score should be printed modulo 998244353998244353.

Constraints

  • 2≤N≤2×1052 \le N \le 2\times 10^5
  • N−1≤M≤2×105N-1 \le M \le 2\times 10^5
  • 1≤Ai,Bi≤N1 \le A_i,B_i \le N
  • 1≤Ci≤91 \le C_i \le 9
  • All input values are integers.
  • It is possible to move from vertex 11 to every other vertex along the edges in their directions.

样例 1 解释:

  • 对于顶点 22,路径 1→121\xrightarrow{1}2 的得分为 11。
  • 对于顶点 33,路径 1→131\xrightarrow{1}3 的得分为 11。
  • 对于顶点 44,路径 1→12→941\xrightarrow{1}2\xrightarrow{9}4 的得分为 1919,路径 1→13→241\xrightarrow{1}3\xrightarrow{2}4 的得分为 1212,因此最小得分为 1212。

因此,按行输出 11、11、1212。

样例 2 解释:

  • 对于顶点 22,路径 1→921\xrightarrow{9}2 的得分为 99,路径 1→221\xrightarrow{2}2 的得分为 22,因此最小得分为 22。
  • 对于顶点 33,路径 1→931\xrightarrow{9}3 的得分为 99,路径 1→22→131\xrightarrow{2}2\xrightarrow{1}3 的得分为 2121,因此最小得分为 99。

注意:所给图中可能包含重边和自环。

样例 3 解释:
注意:得分需对 998244353998244353 取模后输出。

约束条件

  • 2≤N≤2×1052 \le N \le 2\times 10^5
  • N−1≤M≤2×105N-1 \le M \le 2\times 10^5
  • 1≤Ai,Bi≤N1 \le A_i,B_i \le N
  • 1≤Ci≤91 \le C_i \le 9
  • 所有输入值均为整数。
  • 从顶点 11 出发,沿有向边可到达其余每个顶点。

输入解题思路,AI测评打分。不知道怎么写?

首页