問題一覧 > 通常問題

No.1364 [Renaming] Road to Cherry from Zelkova

レベル : / AI推定難易度 : 1550 / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 49
作問者 : 👑 Kazun / テスター : 夕叢霧香(ゆうむらきりか) 37zigen
お気に入りにしたユーザー ProblemId : 5799 / 自分の提出
問題文最終更新日: 2021-01-22 17:30:44
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 279 (Zelkova and Cherry) (順位表) の他の問題:

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.
In particular, for a walk $W=(e_1, \dots, e_k)$, a walk such that $s(e_1)=0, t(e_k)=N$ is called a walk from vertex $0$ to vertex $N$.

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もしくは右上の雲マークをクリックしてアカウントを作成してください。