타임머신

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

요약

가중치가 1인 방향 그래프에서 한 정점에 있는 타임머신이 정해진 정점으로 이동하며 시간을 c만큼 되돌릴 때, 1번에서 N번으로 가는 최소 도착 시간을 구하고 도달 불가능과 무한히 작아지는 경우를 판별한다.

난이도: 보통10점 중 7점
유형: 그래프, 최단 경로, 그리디, 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
```