No.3463 Beltway
レベル :
/ AI推定難易度 : 1500
/ 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 37
作問者 :
t5ugu
/ テスター :
dyktr_06
くらげ
おのせ
hikikomori
tyawanmusi
タグ : / 解いたユーザー数 37
作問者 :
くらげ
hikikomori
問題文最終更新日: 2026-08-30 13:42:56
English (AI translation)
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
MMA Contest 021
(順位表)
の他の問題:
Problem Statement
You are given a simple undirected graph with $V$ vertices and $E$ edges. Edge $i$ $(1 \le i \le E)$ connects vertex $A_i$ and vertex $B_i$.
Among the paths from vertex $S$ to $G$ that use the minimum number of edges, find the maximum value $M$ of the number of "edges contained in some cycle" traversed along the way.
If no such path exists, print -1.
Constraints
- $1 \le V \le 2 \times 10^5$
- $1 \le E \le 2 \times 10^5$
- $1 \le S, G \le V$ and $S \ne G$
- $1 \le A_i, B_i \le V$, where $1 \le i \le E$ and $A_i \ne B_i$
- The given graph is a simple undirected graph.
- All input values are integers.
Input
$V$ $E$ $S$ $G$ $A_1$ $B_1$ $\quad \vdots$ $A_E$ $B_E$
Output
$M$
Print the following value on $1$ line, followed by a newline.
- The maximum number of "edges contained in some cycle" traversed, among the shortest paths from vertex $S$ to $G$
- If no shortest path exists,
-1
Sample
Sample 1
Input
6 6 1 6 1 2 2 3 2 4 4 5 3 6 5 6
Output
2
Among the routes from $1$ to $6$, the one using the fewest edges is " $1 \rightarrow 2 \rightarrow 3 \rightarrow 6$ ".
Of these, the $2$ edges $2 \rightarrow 3$, $3 \rightarrow 6$ are "edges contained in a cycle", so print $2$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。