31723번 - 무빙워크 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 196 | 96 | 75 | 47.771% |
문제
UDP 시티는 $N$개의 건물과 각 건물을 잇는 $M$개의 무빙워크로 이루어져 있다. 각 건물과 무빙워크에는 $1$번부터 차례로 번호가 매겨져 있다. 포닉스는 각 무빙워크의 전원을 끄거나 켤 수 있다. 무빙워크는 전원 상태에 따라 아래와 같이 동작한다.
- $i$번째 무빙워크의 전원이 켜져 있는 경우, $u_i$번 건물에서 $v_i$번 건물로의 방향으로만 이동할 수 있다. 이 경우 이동 시간은 $d_i$이다.
- $i$번째 무빙워크의 전원이 꺼져 있는 경우, $u_i$번 건물과 $v_i$번 건물 사이를 방향에 관계없이 이동할 수 있다. 이 경우 이동 시간은 $2d_i$이다.
포닉스는 현재 $1$번 건물에 있으며, 각 무빙워크의 전원을 적절히 조작해 다른 모든 건물에 대한 최단 도달 시간의 합을 최소화하려 한다. 이때 $1$번 건물에서 도달할 수 없는 건물이 존재해서는 안 된다.
도달할 수 없는 건물이 존재하지 않는 모든 경우에 대해서 모든 건물에 대한 최단 도달 시간의 합의 최솟값과 이때 각 무빙워크의 전원 상태를 구해 보자.
입력
첫째 줄에 건물의 개수 $N$, 무빙워크의 개수 $M$이 공백으로 구분되어 주어진다. $(2 \le N \le 300\ 000; 1 \le M \le 500\ 000)$
둘째 줄부터 $M$개의 줄에 걸쳐 세 정수 $u_i, v_i, d_i$가 공백으로 구분되어 주어진다. 이는 $i$번째 무빙워크의 전원이 켜져 있을 때 $u_i$번 건물에서 $v_i$번 건물으로 이동하는 것이 가능하며 $d_i$의 이동 시간을 가짐을 의미한다. $(1 \le u_i, v_i \le N; u_i \ne v_i; 1 \le d_i \le 10^6)$
모든 무빙워크의 전원을 껐을 때, $1$번 건물에서 다른 모든 건물로 도달할 수 있음이 보장되며 서로 다른 무빙워크에 대해 $(u, v)$ 쌍은 서로 다르다.
출력
첫째 줄에 가능한 최단 도달 시간 합의 최솟값을 출력한다.
둘째 줄에는 각 무빙워크의 전원 상태를 나타내는 정수 $P_1, P_2, \cdots , P_M$을 공백으로 구분해 출력한다. $P_i$는 $i$번째 무빙워크의 전원을 켜야 할 경우 $1$, 꺼야 할 경우 $0$이다. 가능한 전원 상태가 여러 개일 경우 그 중 아무것이나 출력하여라.
예제 입력 1
3 3 1 2 3 3 2 1 1 3 10
예제 출력 1
8 1 0 1
예제 입력 2
3 3 1 2 3 2 3 4 1 3 6
예제 출력 2
9 1 1 1
예제 입력 3
3 3 2 1 3 2 3 4 3 1 6
예제 출력 3
16 0 1 0
예제 입력 4
2 2 1 2 3 2 1 1
예제 출력 4
2 1 0
출처
University > UNIST-DGIST-POSTECH > 2024 UNIST-DGIST-POSTECH 연합 프로그래밍 경진대회 (2024 UDPC) > Senior Division F번
University > UNIST-DGIST-POSTECH > 2024 UNIST-DGIST-POSTECH 연합 프로그래밍 경진대회 (2024 UDPC) > Open Contest I번
- 문제를 만든 사람: leo020630
- 문제를 검수한 사람: 99asdfg, hyperbolic, lky7674, mjhmjh1104, nick832, slah007, tony9402, utilforever