[파이썬] 백준 17940 : 지하철 (골드2)

[파이썬] 백준 17940 : 지하철 (골드2)

• https://www.acmicpc.net/problem/17940

---

---

풀이

방향성 생각

• 조건을 2개 쓰는 다익스트라
• 인접 행렬 -> 인접리스트로 변환 해주기
• 환승 횟수는 최대 N-1이므로 내부 탐색 루프에 조건 걸어주기.
• 힙에 우선순위를 정해놨으면 ex에 도달했을 때 바로 탈출

 

---

전체코드

import heapq as hq
import sys

input = sys.stdin.readline
INF = float('inf')

N,ex = map(int,input().split())
company = [int(input()) for _ in range(N)]

G = [[] for _ in range(N)]
for x in range(N):
    for nx,cost in enumerate(map(int,input().split())):
        if cost:
            G[x].append((nx,cost))

V = [[INF]*N for _ in range(N)]
V[0][0] = 0
heap = [(0,0,0)]
while heap:
    tr,t,x = hq.heappop(heap)

    if x == ex:
        print(tr,V[tr][ex])
        break

    if t > V[tr][x]:
        continue

    for nx,cost in G[x]:
        nt = t + cost
        ntr = tr + (company[nx]!=company[x])
        if nt < V[ntr][nx] and ntr < N-1:
            V[ntr][nx] = nt
            hq.heappush(heap,(ntr,nt,nx))

---

코멘트

• .