[BOJ 23030, Python 3] 후다다닥을 이겨 츄르를 받자!

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

23030번: 후다다닥을 이겨 츄르를 받자!

 

풀이

지문이 좀 길지만 간단하게 정리해보면

노선 N개가 있고, 각 노선내에서 이동하는 경우는 시간이 1이 걸림

환승역에서 다른 노선으로 환승할 때는 T의 시간이 걸림(사람마다 T가 다름)

으로 정리할 수 있습니다.

 

이동하는데 걸리는 시간이 1 또는 T 총 2가지가 있으므로 BFS는 불가능하고, 다익스트라를 사용하여 최단거리 탐색을 할 수 있게 됩니다.

 

역을 저장할 때는 (노선 번호, 역 번호)로 저장을 해야 환승역을 저장할 때 겹치지 않게 저장할 수 있습니다.

 

 

코드

input = __import__('sys').stdin.readline
from heapq import *
 
n = int(input())
station = [*map(int, input().split())]
stations = [[[] for _ in range(station[i])] for i in range(n)]
 
for i in range(n):
    for j in range(station[i]):
        if j - 1 >= 0: stations[i][j].append((i, j-1))
        if j + 1 < station[i]: stations[i][j].append((i, j+1))
 
m = int(input())
for i in range(m):
    p1, p2, q1, q2 = map(int, input().split())
    p1-=1; p2-=1; q1-=1; q2-=1
    stations[p1][p2].append((q1, q2))
    stations[q1][q2].append((p1, p2))
 
for _ in range(int(input())):
    S = [[float('inf')] * station[i] for i in range(n)]
    t, u1, u2, v1, v2 = map(int, input().split())
    u1-=1; u2-=1; v1-=1; v2-=1
    q = []; heappush(q, (u1, u2))
    S[u1][u2] = 0
    while q:
        x, y = heappop(q)
        for nx, ny in stations[x][y]:
            if x == nx and S[nx][ny] > S[x][y] + 1:
                S[nx][ny] = S[x][y] + 1
                heappush(q, (nx, ny))
            elif x != nx and S[nx][ny] > S[x][y] + t:
                S[nx][ny] = S[x][y] + t
                heappush(q, (nx, ny))
    print(S[v1][v2])