시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 479 | 121 | 78 | 21.488% |
신촌 초급반 학생들은 그래프에서 최단 경로를 구하는 여러 방법들을 공부했다. 그들에게 벽을 느끼게 하고 싶었던 djs100201은 무자비한 최단 경로 문제를 만들었다.
$1$번 부터 $N$번까지 번호가 매겨진 총 $N$개의 마을이 있다. $i$번째 마을의 위치는 $(x_i,y_i,z_i)$로 표현된다. $1$이상 $N$이하의 서로 다른 두 정수 $i,j$에 대해, $i$번 마을과 $j$번 마을을 잇는 $\min(|x_i-x_j|,|y_i-y_j|)$만큼의 길이를 가진 양방향 도로가 존재한다. 또한 만약 $z_i+z_j$가 $K$로 나누어 떨어진다면, $i$번 마을과 $j$번 마을을 잇는 $z_i+z_j$의 길이를 가진 양방향 도로 또한 존재한다.
이때 $1$번 마을에서 각 마을로 도착하는 최단 경로의 길이를 모두 구해보자.
첫째 줄에 정수 $N$과 $K$가 공백으로 구분되어 주어진다. $(1 \leq N,K \leq 200\,000)$
둘째 줄부터 $N$개의 줄에 걸쳐 $i+1$번째 줄에는 $i$번 마을의 위치를 나타내는 세 정수 $(x_i,y_i,z_i)$가 공백으로 구분되어 주어진다. $(0 \leq x_i,y_i,z_i \leq 10^9)$
총 $N$줄에 걸쳐 답을 출력한다. $i$번째 줄에는 $i$번 마을에 도착하는 최단 경로의 길이를 출력한다.
3 4 0 0 0 1 1 3 100 100 5
0 1 9
3 2 1 2 3 3 4 1 1 2 3
0 2 0