[백준 알고리즘] 27008번: Checking an Alibi (Python)

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

27008번: Checking an Alibi

 

소스코드

import sys
import heapq as hq
input = sys.stdin.readline

def dijkstra(start):
  q = []
  min_dis[start] = 0
  hq.heappush(q,[0,start])

  while q:
    cur_dis,cur_node = hq.heappop(q)
    
    if min_dis[cur_node] < cur_dis:
      continue

    for next_node,next_dis in graph[cur_node]:
      if min_dis[next_node] > cur_dis + next_dis:
        min_dis[next_node] = cur_dis + next_dis
        hq.heappush(q,[cur_dis+next_dis,next_node])
    
f,p,c,m = map(int,input().split())
graph = [[] for _ in range(f+1)]
min_dis = [float('inf') for _ in range(f+1)]
for _ in range(p):
  a,b,t = map(int,input().split())
  graph[a].append([b,t])
  graph[b].append([a,t])

dijkstra(1)
ans = []
for i in range(1,c+1):
  k = int(input())
  if min_dis[k] <= m:
    ans.append(i)

print(len(ans))
for x in ans:
  print(x)

 

 

풀이

★ 다익스트라 문제들 쭉 보다가 제목이 흥미롭기도 했고, 영어지문으로 된 문제에 한번 도전해보고 싶어서 풀어봤습니다

 

★  확실히 지문이 영어라 이해하는 데 어려움이 있었던 거 같아요. 하지만 문제 자체는 어렵지 않았습니다. 그냥 헛간이 있는 위치에서부터 소들이 있는 위치까지의 거리가 m이하라면 그 소는 범인이 될 수 있기 때문에 확인해주는 풀이방식입니당 :)