백준 31723번: 무빙워크 (Python)

문제링크

https://www.acmicpc.net/problem/31723

문제 총평

- 평범한 다익스트라에 아이디어 조금 첨가

문제 접근방식

- 이 문제에 경우 사실 간단합니다.

- 먼저 평범한 다익스트라 처럼 간선을 받아주고 무빙워크의 반대 방향으로는 *2의 길이로 받아줍니다.

- 이때 이 간선들은 버리지 말고 나중 출력을 위해 따로 모아 놓습니다.

- 그리고 다익스트라를 돌리면 1에서부터의 모든 정점의 거리가 나옵니다.

- 이때 따로 모아 놓았던 간선을 확인 합니다.

경우의 수

1. dist[u] >= d[v] 인 경우

2. dist[u] < d[v] 인 경우

- 이 두 경우에서 2번을 주목하면 되는데 dist[u] < d[v]라는거는 정점 1에서 u 정점으로 간 이후 u 정점에서 임의의 경로를 통해 d[v] 로 이동했다는 뜻입니다. 즉, 이경우 방향이 u -> v 이므로 무빙워크를 키는게 반드시 이득입니다.

- 1번의 경우에는 v -> u 로 이동하였기 때문에 무빙워크의 반대 방향이므로 이 경우 무빙워크를 끄는게 이득입니다.

- 물론 끄거나 키거나 같은 결과가 나올 수도 있으나 이 문제는 스페셜저지 문제이므로 신경쓰지 않습니다.

 

 

 

정답코드 

import sys; input = sys.stdin.readline
import heapq as h
n, m = map(int, input().split())
arr = [[] for _ in range(n+1)]
moving = []
for _ in range(m):
    a,b,c = map(int, input().split())
    moving.append((a,b))
    arr[a].append((b,c))
    arr[b].append((a,c<<1))

d = [0,0] + [int(1e12)]*(n-1)

q = []
h.heappush(q, (0, 1))

while q:
    dist, now = h.heappop(q)
    if d[now] < dist: continue
    for x,y in arr[now]:
        cost = y + d[now]
        if cost < d[x]:
            d[x] = cost
            h.heappush(q,(cost,x))
print(sum(d[1:]))
for x,y in moving:
    if d[x] < d[y]:
        print("1",end=" ")
    else:
        print("0", end=" ")

문제 풀이 후 생각

- 어찌보면 정말 간단하지만 대회 당시에 이런걸 생각하기에는 난이도가 상당해 보입니다.