시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 1380 | 389 | 274 | 27.565% |
키르는 마을가 $N$개 있는 나라에 살고 있다. 편의상 1번부터 $N$번 까지의 마을이라고 하자. 이들은 두 마을을 잇는 $M$개의 도로로, 양방향으로 연결되어 있다.
키르는 $S$번 마을에서 $E$번 마을까지 가려고 한다. 항상 같은 길로만 가던 키르는 다른 길도 걸어 보고 싶었다. 그래서 키르는 $S$번 마을에서 $E$번 마을까지 가는 경로중 서로 다른 최단경로가 몇 개 있는지 궁금했다. 어떤 두 경로가 다르다는 것은, 한 경로에서는 사용한 도로를 다른 경로에서 사용하지 않았거나, 그 반대를 말한다.
키르의 궁금증을 해소해 주자!
첫째 줄에는 $N$, $M$, $S$, $E$가 하나의 공백으로 구분되어 들어온다. ($2 \le N \le 100000$, $N-1 \le M \le 300000$, $1 \le S, E \le N$, $S \neq E$) 그 후 $M$개의 줄에는 $A$, $B$, $C$가 하나의 공백으로 구분 되어 들어 오는데, 이는 도로가 $A$부터 $B$까지를 양방향으로 이으며, 도로의 길이가 $C$라는 것을 의미한다. ($1 \le A, B \le N, 1 \le C \le 1000000000$)
$S$에서 $E$까지 가는 최단 경로의 가짓수를 1000000009($10^9 + 9$)로 나눈 나머지를 구하여라.
3 4 1 3 1 2 1 2 1 1 2 3 1 1 3 2
3