F. 邪恶最短路径

SMBC 编程竞赛 #2（第 481 场 AtCoder Beginner Contest）

邪恶最短路径

Evil Shortest Path

AtCoder

⌀ 1621

原题

← EG →

邪恶最短路径AI (CI翻译)

Problem Statement

题目描述

AI (CI翻译)

You are given a directed graph with $N$ vertices and $M$ edges. The vertices are numbered $1,2,\ldots,N$ . The $i$ -th edge goes from vertex $A_i$ to vertex $B_i$ , and a digit $C_i$ between $1$ and $9$ , inclusive, is written on this edge.

给定一个有向图，包含 $N$ 个顶点和 $M$ 条边。顶点编号为 $1,2,\ldots,N$ 。第 $i$ 条边从顶点 $A_i$ 指向顶点 $B_i$ ，边上标有一个介于 $1$ 和 $9$ （含）之间的数字 $C_i$ 。AI (CI翻译)

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.

沿边的方向移动时，按照经过边的顺序，将这些边上标记的数字拼接得到的整数称为这次移动的得分。例如，若经过的边上依次标有数字 $3,1,4$ ，则这次移动的得分为 $314$ 。同一个顶点或同一条边可以经过多次。AI (CI翻译)

For each $v=2,3,\ldots,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.

对于每个 $v=2,3,\ldots,N$ ，求从顶点 $1$ 移动到顶点 $v$ 所能得到的最小得分，并对 $998244353$ 取模。保证给定的有向图中，从顶点 $1$ 出发可以沿边的方向到达每个其他顶点。AI (CI翻译)

Constraints

约束条件

AI (CI翻译)

$2 \le N \le 2\times 10^5$
$N-1 \le M \le 2\times 10^5$
$1 \le A_i,B_i \le N$
$1 \le C_i \le 9$
All input values are integers.
It is possible to move from vertex $1$ to every other vertex along the edges in their directions.

$2 \le N \le 2\times 10^5$
$N-1 \le M \le 2\times 10^5$
$1 \le A_i,B_i \le N$
$1 \le C_i \le 9$
所有输入值均为整数。
从顶点 $1$ 出发可以沿边的方向到达每个其他顶点。

AI (CI翻译)

Input

输入格式

AI (CI翻译)

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

输入从标准输入按以下格式给出：AI (CI翻译)

N M
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_M B_M C_M

N M
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_M B_M C_M

AI (CI翻译)

Output

输出格式

AI (CI翻译)

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

输出 $N-1$ 行。第 $(v-1)$ 行应包含顶点 $v$ 对应的答案。AI (CI翻译)

样例

Input #1

Output #1

1
1
12

- For vertex $2$, $1\xrightarrow{1}2$ gives a score of $1$. - For vertex $3$, $1\xrightarrow{1}3$ gives a score of $1$. - For vertex $4$, $1\xrightarrow{1}2\xrightarrow{9}4$ gives a score of $19$, and $1\xrightarrow{1}3\xrightarrow{2}4$ gives a score of $12$, so the minimum is $12$. Thus, print $1, 1, 12$, separated by newlines.

Input #2

Output #2

2
9

- For vertex $2$, $1\xrightarrow{9}2$ gives a score of $9$, and $1\xrightarrow{2}2$ gives a score of $2$, so the minimum is $2$. - For vertex $3$, $1\xrightarrow{9}3$ gives a score of $9$, and $1\xrightarrow{2}2\xrightarrow{1}3$ gives a score of $21$, so the minimum is $9$. Note that the given graph may contain multi-edges and self-loops.

Input #3

Output #3

Note that the score should be printed modulo $998244353$.

题目信息

题号

abc481_f

所属比赛

SMBC 编程竞赛 #2（第 481 场 AtCoder Beginner Contest）

时间限制

2 s

内存限制

1024 MB

题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。