BOJ - 9370. 미확인 도착지

www.acmicpc.net/problem/9370

9370번: 미확인 도착지

 

1. S. G. H을 시작점으로 하여 3번에 걸쳐 다익스트라:

import sys
from heapq import heappush, heappop
for _ in range(int(input())):
    n, m, t = map(int, input().split())
    s, g, h = map(int, input().split())
    road = [[] for _ in range(n + 1)]
    for _ in range(m):
        a, b, c = map(int, sys.stdin.readline().split())
        road[a].append((b, c))
        road[b].append((a, c))
    ds = {}
    for i in (s, g, h):
        d = [1000 * n] * (n + 1)
        d[i] = 0
        q = [(0, i)]
        while q:
            _, a = heappop(q)
            for b, c in road[a]:
                if d[b] > d[a] + c:
                    d[b] = d[a] + c
                    heappush(q, (d[b], b))
        ds[i] = d
    ans = []
    for _ in range(t):
        i = int(input())
        if ds[g][h] + min(ds[s][g] + ds[h][i], ds[s][h] + ds[g][i]) == ds[s][i]:
            ans.append(i)
    ans.sort()
    print(*ans)

 

2. G, H를 지나는 도로에 한해 가중치 조작:

import sys
from heapq import heappush, heappop
for _ in range(int(input())):
    n, m, t = map(int, input().split())
    s, g, h = map(int, input().split())
    road = [[] for _ in range(n + 1)]
    for _ in range(m):
        a, b, c = map(int, sys.stdin.readline().split())
        if a == g or a == h:
            c -= .18
        if b == g or b == h:
            c -= .18
        if (a, b) == (g, h) or (a, b) == (h, g):
            c -= .18
        road[a].append((b, c))
        road[b].append((a, c))
    d = [1000 * n] * (n + 1)
    v = [0] * (n + 1)
    q = [(0, s)]
    while q:
        p, a = heappop(q)
        if not v[a]:
            v[a] = 1
            d[a] = p
            for b, c in road[a]:
                heappush(q, (p + c, b))
    ans = []
    for _ in range(t):
        i = int(input())
        p = d[i]
        if type(p) is float and int(p) == round(p):
            ans.append(i)
    ans.sort()
    print(*ans)

2번 코딩에서,

최단 경로가 아래 경우이면 가능:
g > h
@ > g, g > h, h > @
@ > g, g > h
@ > g, g > @, @ > h
@ > g, g > @, @ > h, h > @
...
그 외의 경우에서는 불가능.

불가능한 경우에서 조작된 가중치를 가장 많이 거치는 건 2번.
g > h의 경우에서는 가능하게 만들어야 하기 때문에,
g > h의 가중치는 @ > g, @ > h의 가중치의 2배보다 크도록 설정.