타임머신

시간 제한1초메모리 제한1024 MB

요약

1번 정점에서 출발해 a에서 b로 가는 시간 기계를 쓰면 시계가 c만큼 되돌아가는 조건에서, N번 정점의 최소 도착 시각을 구합니다. 도달할 수 없거나 시각이 무한히 작아지면 그렇게 판별합니다.

난이도: 보통10점 중 6점
유형: 최단 경로, 그래프, BFS
정답자: 아직 제출이 없습니다

문제

정점이 $N$ 개, 간선이 $M$ 개인 방향 그래프가 주어진다. 각 간선을 따라 이동하는 데 걸리는 시간은 $1$ 이다. $a$ 번 정점에는 타임머신이 있다. 타임머신을 이용하면 $b$ 번 정점으로 이동하고, 시간이 $c$ 만큼 되돌아간다. 타임머신을 이용하는 횟수에는 제한이 없다. 시간 $0$ 에 $1$ 번 정점에서 출발하여 $N$ 번 정점에 도착하는 시간의 최솟값을 구하여라. 단, $N$ 번 정점에 도착한 뒤에도 계속 움직일 수 있다.

입력

첫째 줄에 $N$ , $M$ , $a$ , $b$ , $c$ 가 공백으로 구분되어 주어진다. $(1 \leq N,M \leq 200\ 000; 1 \leq a,b \leq N; 1 \leq c \leq 10^9)$

둘째 줄부터 $M+1$ 번째 줄까지 $i+1$ 번째 줄에는 두 정수 $u_i$ , $v_i$ 가 주어진다. 이는 $i$ 번째 간선이 $u_i$ 에서 $v_i$ 로 이동하는 간선임을 뜻한다. $(1 \leq u_i, v_i \leq N; u_i \neq v_i)$

출력

첫째 줄에 도착시간의 최솟값을 출력한다. $N$ 번 정점까지 가는 것이 불가능하면 x를, 도착시간을 무한히 작게 만드는 것이 가능하면 -inf를 출력한다.

예제3

예제 1
입력
```
5 4 3 4 2
1 2
2 3
2 4
4 5
```
예상 출력
```
1
```
예제 2
입력
```
5 3 3 4 2
1 2
2 3
2 4
```
예상 출력
```
x
```
예제 3
입력
```
5 4 4 3 3
1 2
3 2
2 4
4 5
```
예상 출력
```
-inf
```