問題一覧 > 通常問題

No.3463 Beltway

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 37
作問者 : t5ugu / テスター : dyktr_06 くらげ おのせ hikikomori tyawanmusi
お気に入りにしたユーザー ProblemId : 13081 / 自分の提出
問題文最終更新日: 2026-08-30 13:42:56
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もしくは右上の雲マークをクリックしてアカウントを作成してください。