Bessla 모터스

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

요약

가중치가 있는 도로 그래프에서 충전소 K곳 이상으로부터 거리 R 이내에 있는 여행지를 찾아 개수와 목록을 오름차순으로 출력합니다.

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

문제

Farmer John은 Bessla 전기 트랙터를 홍보하려고 한다. 그래서 Bessla 충전소 네트워크를 보여 주려 한다. 관심 지점은 $N$ 개( $2\le N\le 5\cdot 10^4$ )이며 $1\dots N$ 으로 번호가 붙어 있다. 앞의 $C$ 개( $1\le C < N$ )는 충전소이고, 나머지는 여행 목적지다. 지점들은 $M$ 개( $1\le M\le 10^5$ )의 양방향 도로로 연결되어 있다. $i$ 번째 도로는 서로 다른 지점 $u_i$ 와 $v_i$ 를 잇고, 길이는 $\ell_i$ 마일( $1\le\ell_i\le 10^9$ )이다.

베슬라는 한 번 충전으로 최대 $2R$ 마일( $1\le R\le 10^9$ )을 이동할 수 있어서, 충전소에서 $R$ 마일 이내에 있는 모든 목적지에 도달할 수 있다. 목적지가 $K$ 개( $1\le K\le 10$ ) 이상의 서로 다른 충전소에서 도달 가능하면 well-connected하다고 한다. well-connected한 여행 목적지의 집합을 구하라.

입력

첫 줄에 다섯 정수 $N$ , $M$ , $C$ , $R$ , $K$ 가 공백으로 구분되어 주어진다. 이어지는 $M$ 개의 줄에는 각각 세 정수 $u_i$ , $v_i$ , $\ell_i$ 가 공백으로 구분되어 주어지며, $u_i\neq v_i$ 이다.

충전소는 $1, 2, \ldots, C$ 번이다. 나머지 지점은 모두 여행 목적지다.

출력

먼저 well-connected한 여행 목적지의 개수를 한 줄에 출력한다. 이어서 그 목적지를 오름차순으로 한 줄에 하나씩 출력한다.

예제3

예제 1
입력
```
3 3 1 4 1
1 2 3
1 3 5
2 3 2
```
예상 출력
```
1
2
```
예제 2
입력
```
4 3 2 101 2
1 2 1
2 3 100
1 4 10
```
예상 출력
```
2
3
4
```
예제 3
입력
```
4 3 2 100 2
1 2 1
2 3 100
1 4 10
```
예상 출력
```
1
4
```