백준 18352 파이썬 특정 거리의 도시 찾기

링크 : https://www.acmicpc.net/problem/18352

18352번: 특정 거리의 도시 찾기

 

bfs로도 풀 수 있을것 같은데?? 에서 시간 초과가 날 것 같아서 그냥 바로 다익스트라로 직행했다.

 

적당히 다익스트라 를 적용했다. 노드에서 노드로 가는 가중치가 전부 1 이므로 어렵지 않았다.

import sys
import heapq

n,m,k,start = map(int,input().split())
INF = sys.maxsize
input = sys.stdin.readline

city = [[] for i in range(n+1)]
dp=[INF]*(n+1)

for i in range(m):
    v,c = map(int,input().split())

    city[v].append((1,c))

heap = []

def dijkstra(start):
    dp[start] = 0

    heapq.heappush(heap,(0,start))

    while heap:
        w,now = heapq.heappop(heap)

        if dp[now] < w:
            continue

        for w_node, node in city[now]:

            newx_w = w+ w_node

            if newx_w < dp[node]:
                dp[node] = newx_w

                heapq.heappush(heap,(newx_w,node))

dijkstra(start)

result= 0

for i in range(len(dp)):
    if dp[i] == k:
        print(i)
        result += 1

if result == 0:
    print(-1)