지하철 환승
실버 III의견: 0
리세시에는 \(N\)개의 지하철 역과 \(M\)개의 노선이 있다. 각 노선은 두 역을 양방향으로 연결하며, 같은 두 역을 연결하는 노선이 여러 개 있을 수 있다.
승객이 역 \(S\)에서 역 \(T\)로 이동하려 한다. 이동할 때마다 현재 역에서 노선 하나를 타고 인접한 역으로 이동하며, 이를 1번 이동이라 한다. 최소 이동 횟수를 구하여라. 역 \(T\)에 도달할 수 없으면 \(-1\)을 출력한다.
- \(1 \le N \le 100\,000\)
- \(0 \le M \le 200\,000\)
- \(1 \le u, v \le N\), \(u \ne v\)
- \(1 \le S, T \le N\)
첫째 줄에 역의 수 \(N\)과 노선의 수 \(M\)이 공백으로 구분되어 주어진다.
다음 \(M\)개의 줄에 노선이 연결하는 두 역 번호 \(u\), \(v\)가 공백으로 구분되어 주어진다.
마지막 줄에 출발 역 \(S\)와 도착 역 \(T\)가 공백으로 구분되어 주어진다.
역 \(S\)에서 역 \(T\)까지의 최소 이동 횟수를 출력한다. 도달할 수 없으면 \(-1\)을 출력한다.
5 4
1 2
2 3
3 4
4 5
1 5
4
역 \(1 \to 2 \to 3 \to 4 \to 5\)로 최소 \(4\)번 환승합니다.
4 4
1 2
2 3
3 4
1 4
1 4
1
\(1 \to 4\) 직통 연결이 있으므로 \(1\)번 환승으로 갈 수 있습니다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
지하철 환승
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
지하철 환승