파댕이컵 G: 직장인 파댕이의 사회생활

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

문제

파댕이는 중견기업 회사에서 직장인으로 일하고 있다. 사장님이 직장인 파댕이를 무척 아끼기 때문에, 파댕이는 사장실에 찾아가 사장님께 인사를 하려고 한다.

직장인 파댕이의 회사가 있는 건물은 K층으로 구성되어 있는데 각 층은 방과 복도로 구성되어 있다. 복도를 통해 방과 방 사이를 양방향으로 이동할 수 있다. 모든 층은 같은 모습을 하고 있다. 파댕이는 현재 1층의 1번 방에 있고, 사장실은 K층의 N번 방이다. 파댕이는 현재 자신의 위치에서부터 사장실까지 최소 시간을 사용하여 도착할 방법을 찾아야 한다.

파댕이는 각각의 복도를 지나가는 데 걸리는 시간이 얼마인지 알고 있다. 더불어 어떤 방에는 엘리베이터가 있어서 그 엘리베이터를 타고 위층으로 올라갈 수 있다. 한 층의 i번 방에 설치된 엘리베이터는 다른 층에 있는 모든 i번 방을 연결한다. 특정 엘리베이터에만 사람이 몰릴 수 있기 때문에 어떤 엘리베이터는 빠르고 어떤 엘리베이터는 느릴 수 있다. 파댕이는 각각의 엘리베이터가 한 층을 올라가는 데 걸리는 시간이 얼마인지도 알고 있다.

건물의 모습과 엘리베이터의 속도가 주어지면, 파댕이가 사장실까지 가는 최소 시간을 계산하는 프로그램을 작성하시오.

입력

첫째 줄에 방의 수 N (2 ≤ N ≤ 100,000)과 복도의 수 M (1 ≤ M ≤ 300,000), 건물의 층수 K (2 ≤ K ≤ 200,000)가 공백으로 구분되어 주어진다.

다음 줄부터 M개의 줄에 걸쳐 세 정수 u, v, c가 공백으로 구분되어 주어진다. (1 ≤ u, v ≤ N, 1 ≤ c ≤ 100,000,000, u ≠ v) 이는 u번 방과 v번 방을 잇는 복도가 존재하며 이를 지나가는 데 걸리는 시간이 c라는 뜻이다.

임의의 서로 다른 두 방에 대해 한쪽 방에서 다른 쪽 방으로 이어진 복도는 1개 이하다.

다음 줄에 N개의 정수 e₁, …, e_N이 공백으로 구분되어 주어진다. (e_i = -1 or 1 ≤ e_i ≤ 100,000,000) 이는 i번째 방에 존재하는 엘리베이터를 타면 한 층을 올라갈 때마다 e_i의 시간이 든다는 뜻이다. 만약 i번째 방에 엘리베이터가 존재하지 않는다면, e_i = -1이다.

출력

파댕이가 사장실까지 가는 최소 시간을 출력한다. 만약 파댕이가 사장실에 도달할 수 없다면 
-1을 출력한다.

 

---

풀이

파댕이가 사장님을 만나러 가도 좋지만 진취적으로 생각해서 사장님이 파댕이를 만나러 가도 되는 문제다. 둘이 같이 이동해서 걸린 시간만 합해준다면, 파댕이가 혼자 사장님 방까지 가는 것이나, 사장님이 파댕이에게 오는 것이나, 둘 다 움직여서 같은 번호의 방으로 와 엘베만 타면 만날 수 있게 되는 것이나 똑같다. 둘 다 같은 방으로 오도록 해서 엘베 타는 시간만 더해주는 것으로 문제 풀이의 방향을 잡았다.

 

먼저 파댕이가 1번 방에서 출발해서 모든 방까지 이동하는 가장 빠른 경로를 찾는다. 각 복도의 가중치가 모두 양수이기 때문에 데익스트라 알고리즘으로 처리 가능하다. 사장님은 N번 방에서 출발해 모든 방까지 이동하는 가장 빠른 경로를 찾아 저장한다.

 

파댕이와 사장님이 i번째 방으로 이동하는데 걸린 시간을 각각 더하고, i번째 방의 엘리베이터가 K층을 이동하는데 걸리는 시간인 i*(K-1)을 더해주면 된다. 이렇게 얻은 총 이동 시간 값을 길이 N의 배열에 따로 관리한다.

 

이때, 만약 파댕이나 사장님 둘 중 하나라도 i번째 방으로 올 수 있는 방법이 없거나, i번째 방에 엘베가 없다면 i번째 방을 통해서는 사장님 방으로 갈 수 없다.

 

시간 값 중 -1이 아닌 가장 적은 값을 찾아 출력한다. 만약 -1이 아닌 값이 없다면 갈 방법이 아예 없는 것이니 -1을 출력한다.

 

 

정답 코드

import sys
import heapq
input = sys.stdin.readline
INF = sys.maxsize
N,M,K = map(int,input().split())

# 복도의 가중치 관리
corridor = dict()
for n in range(N):
    corridor[n+1] = []
for m in range(M):
    u,v,c = map(int,input().split())
    corridor[u].append([v,c])
    corridor[v].append([u,c])
    
ev = list(map(int, input().split()))
ev.insert(0,-1)

# 파댕이와 사장님의 방 도착 시간 초기화
padaeng = [INF] * (N + 1)
ceotime = [INF] * (N + 1)
padaeng[1] = 0
ceotime[N] = 0
padaengq = []
ceoqueue = []

# 데익스트라
heapq.heappush(padaengq, (0,1))
heapq.heappush(ceoqueue, (0,N))
while padaengq:
    dist, now = heapq.heappop(padaengq)
    if padaeng[now] < dist:
        continue
    for i in corridor[now]:
        cost = dist+i[1]
        if cost < padaeng[i[0]]:
            padaeng[i[0]] = cost
            heapq.heappush(padaengq,(cost,i[0]))
while ceoqueue:
    dist, now = heapq.heappop(ceoqueue)
    if ceotime[now] < dist:
        continue
    for i in corridor[now]:
        cost = dist+i[1]
        if cost < ceotime[i[0]]:
            ceotime[i[0]] = cost
            heapq.heappush(ceoqueue,(cost,i[0]))
            
# 가장 시간 적게 걸리는 방 찾아서 출력
result = [INF]*(N+1)
for i in range(1,N+1):
    if ev[i] > -1 and padaeng[i] < INF and ceotime[i] < INF:
        result[i] = padaeng[i]+ceotime[i]+ev[i]*(K-1)
if min(result) == INF:
    print(-1)
else:
    print(min(result))