No.1364 [Renaming] Road to Cherry from Zelkova
タグ : / 解いたユーザー数 49
作問者 : 👑
Kazun
/ テスター :
夕叢霧香(ゆうむらきりか)
37zigen
Note
The problems of yukicoder contest 279 (Zelkova and Cherry) are not sorted in order of difficulty. Therefore, it is strongly recommended that you choose which problems to attempt based on publicly available information, such as the problem statements, the number of stars indicating difficulty, and the number of accepted solvers.
Problem Statement
There is a directed graph consisting of $N+1$ vertices numbered from $0$ to $N$ and some directed edges. For each $j=1, \dots, M $, this graph has $a_j$ directed edges of length $l_j$ from vertex $u_j$ to vertex $v_j$. Note that this directed graph has no self-loops. Consider all walks from vertex $0$ to vertex $N$ in this graph. If the sum of their lengths is finite, find the sum modulo $10^9+7$; if it is infinite, report that fact. Note that 2 walks are considered different if the edges used are not the same, even if the order of the visited vertices is the same.
Translator's Note
For a directed edge $e$, let $s(e), t(e)$ denote the start point and the end point of $e$, respectively. Then, for a directed edge $e$, if $s(e)=t(e)$, the edge $e$ is called a self-loop.
A sequence of edges $e_1, \dots, e_k$ is said to form a walk $W=(e_1, \dots, e_k)$ if it satisfies the following.
- For $i=1, \dots, k-1$, $t(e_i)=s(e_{i+1})$ holds.
For a walk $W=(e_1, \dots, e_k)$, letting the length of an edge $e$ be $l(e)$, the length $l(W)$ of the walk $W$ is defined as $l(W)=\sum_{i=1}^k l(e_i)$.
Constraints
- $1 \leq N \leq 10^5$
- $1 \leq M \leq 2 \times 10^5$
- $0 \leq u_j, v_j \leq N$
- $u_j \neq v_j$
- $1 \leq l_j \leq 10^9$
- $1 \leq a_j \leq 10^9$
- All inputs are integers.
Input
$N\ M$ $u_1\ v_1\ l_1\ a_1$ $\vdots$ $u_M\ v_M\ l_M\ a_M$
Output
If the sum of the lengths of the walks from vertex $0$ to vertex $N$ is finite, output the sum modulo $10^9+7$. If it is infinite, output INF.
In either case, do not forget the newline at the end.
Sample
Sample 1
Input
3 4 0 1 2 1 1 2 1 1 2 3 3 1 0 3 4 1
Output
10
The walk $0 \to 1 \to 2 \to 3$ of length $6$ and the walk $0 \to 3$ of length $4$, these 2 walks, have a total length of $10$.
Sample 2
Input
3 4 0 1 1 1 1 2 1 1 2 1 1 1 2 3 1 1
Output
INF
For any positive integer $n$, there exists a walk that goes back and forth between vertex $1$ and vertex $2$ $n$ times. Therefore, the sum of the lengths is infinite.
Sample 3
Input
1 2 0 1 3 2 0 1 4 3
Output
18
The length of an edge connecting 2 vertices is not necessarily unique.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。