할로윈 묘지

• 음수 가중치가 있는 그래프에서 최단경로를 구하는 단순한 문제이다. 단일 출발지 최단 경로 (Single Source Shortest Path)에서 설명한대로 SPFA를 쓰면 된다.
• 하지만, 비슷한 다른 문제들이 골드인데 반해 이 문제만 플래티넘으로 책정된 것은, 지문 이해의 난이도가 크기 때문이다. 우선 가급적이면 문제를 한글 번역 대신에 영어 원문으로 읽도록 하자. 완벽하진 않지만 애매한 부분을 많이 줄여준다.
• 그래프가 그리드 형태로 주어지는 것은 별로 특별한 것은 아니다. 그냥 (x,y)자체를 key로 주고 만들어도 되지만, 정수로 변환해서 그래프를 만들어서 풀었다.
• 문제가 애매한 것은 'Never'을 출력하는 조건이, 어떻게든 음수 사이클에 도달할 방법이 있다면 해당하는 건지, 도착 노드로 가는 경로 안에 음수 사이클이 존재한다면 해당하는 것인지이다. 이 문제에서는 전자가 맞다
• 그리고 애매하진 않지만 실수하기 쉬운 것은, 도착 노드에 도착한 순간 종료한다는 것이다. 도착노드를 포함하는 음수 사이클은 무시해야 한다는 뜻인데, 그냥 도착노드에서는 다른 노드로 가는 엣지를 만들지 않으면 해결할수 있다.
• 총 시간 복잡도는 O(VE)에서, V=W*H 이고, 어떤 노드에서 나가는 엣지는 노드가 잔디일때 최대 4개, 귀신구멍일때는 1개이므로, 총 엣지수는 O(V)이다. 결국 O(VE) = O(V^2) = O(W^2*H*2).

"""Solution code for "BOJ 3860. 할로윈 묘지".

- Problem link: https://www.acmicpc.net/problem/3860
- Solution link: http://www.teferi.net/ps/problems/boj/3860

Tags: [SPFA]
"""

import sys
from teflib import tgraph

INF = float('inf')


def main():
    while True:
        W, H = [int(x) for x in sys.stdin.readline().split()]
        if W == H == 0:
            break

        G = int(sys.stdin.readline())
        graves = set()
        for _ in range(G):
            X, Y = [int(x) for x in sys.stdin.readline().split()]
            graves.add(Y * W + X)

        wgraph = [{} for _ in range(W * H)]
        E = int(sys.stdin.readline())
        for _ in range(E):
            X1, Y1, X2, Y2, T = [int(x) for x in sys.stdin.readline().split()]
            source, dest = Y1 * W + X1, Y2 * W + X2
            wgraph[source][dest] = T

        for source, edges in enumerate(wgraph):
            if wgraph[source]:  # haunted hole exists
                continue
            y, x = divmod(source, W)
            for dx, dy in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
                nx, ny = x + dx, y + dy
                dest = ny * W + nx
                if 0 <= nx < W and 0 <= ny < H and dest not in graves:
                    edges[dest] = 1
        wgraph[W * H - 1].clear()

        dists = tgraph.spfa(wgraph, 0)
        if -INF in dists:
            print('Never')
        else:
            dist_to_dest = dists[W * H - 1]
            print('Impossible' if dist_to_dest == INF else dist_to_dest)


if __name__ == '__main__':
    main()

• Dependency: teflib.tgraph.spfa