RiseOJ – 베슬라 모터스

설명

*참고: 이 문제의 시간 제한은 기본의 1.5배인 3초이고, 메모리 제한은 기본의 두 배인 512MB이다.*

농부 존은 베슬라(Bessla) 전기 트랙터 제품군을 홍보하기 위해 베슬라의 충전소 네트워크를 선보이려 한다. 그는 $1\dots N$ 의 라벨이 붙은 $$N$$ ( $2\le N\le 5\cdot 10^4$ )개의 관심 지점을 정했는데, 그중 처음 $$C$$ ( $1\le C < N$ )개는 충전소이고 나머지는 여행지이다. 이 관심 지점들은 $$M$$ ( $1\le M\le 10^5$ )개의 양방향 도로로 서로 연결되어 있으며, $$i$$ 번째 도로는 서로 다른 지점 $$u_i$$ 와 $$v_i$$ ( $1\le u_i, v_i\le N$ )를 연결하고 길이는 $\ell_i$ 마일 ( $1\le\ell_i\le 10^9$ )이다.

베슬라는 한 번 충전으로 최대 $$2R$$ 마일 ( $1\le R\le 10^9$ )을 주행할 수 있으므로, 충전소에서 $$R$$ 마일 이내의 어떤 여행지든 도달할 수 있다. 적어도 $$K$$ ( $1\le K\le 10$ )개의 서로 다른 충전소에서 도달할 수 있는 여행지를 연결이 좋은 여행지라 한다. 연결이 좋은 여행지들의 집합을 찾아 농부 존을 도와주는 것이 당신의 일이다.

출제: Alexander Wei

제약

배점

입력 4, 5: $$K = 2$$ , $N \le 500$ , $M\le 1000$ .
입력 6, 7: $$K = 2$$ .
입력 8-15: 추가 제약 없음.

출제: Alexander Wei

입력 형식

첫째 줄에 공백으로 구분된 다섯 정수 $$N$$ , $$M$$ , $$C$$ , $$R$$ , $$K$$ 가 주어진다. 다음 $$M$$ 개의 줄에 각각 $u_i\neq v_i$ 인, 공백으로 구분된 세 정수 $$u_i$$ , $$v_i$$ , $\ell_i$ 가 주어진다.

충전소는 $1, 2, \ldots, C$ 의 라벨이 붙어 있다. 나머지 관심 지점은 모두 여행지이다.

출력 형식

먼저 연결이 좋은 여행지의 개수를 한 줄에 출력한다. 그다음 연결이 좋은 모든 여행지를 오름차순으로 한 줄에 하나씩 출력한다.

예제 1

입력

출력

1
2

설명

We have one charging station at $$1$$ . From this charging station, we can reach
point $$2$$ (since it is distance $$3$$ away from $$1$$ ), but not point $$3$$ (since it
is distance $$5$$ away from $$1$$ ). Thus, only point $$2$$ is well-connected.

예제 2

입력

4 3 2 101 2
1 2 1
2 3 100
1 4 10

출력

2
3
4

설명

We have charging stations at $$1$$ and $$2$$ , and both points $$3$$ and $$4$$ are within
distance $$101$$ of both $$1$$ and $$2$$ . Thus, both points $$3$$ and $$4$$ are well-connected.

예제 3

입력

4 3 2 100 2
1 2 1
2 3 100
1 4 10

출력

1
4

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2023-2024 > February > Gold

올림피아드 > USACO > 2023-2024 > February > Gold

태그

JudgeUSACO

베슬라 모터스

평가 및 의견

풀이 제출