t_전보_262

문제

N개의 도시
a to b로 전보 보낼라면 a to b통로가 있어야함
각각 통로마다 보내는 시간이 있음
c출발하여 최대한 많이 퍼저 나갈것.

답

각 통로마다 보내는 시간이 없으면 bfs로 해결이 가능할 것이다.
실수한부분

1. heapq에서는 우선순위로 두고싶은걸 앞에둬야한다!
2. 큐에담겨있으므로 앞에 더 짧은 비용이 온것들이 왔을수 있다.
   • 나의 생각상으로는 인접 노드들 불러오는 for문안에 sum이 더작은가 하는 if문에서 걸러지긴하지만
   • 시간복잡도상으로는 이전에 더 짧은 시간이 온경우에는 continue처리해주는게 좋을것같다.

import heapq

input = """
3 2 1
1 2 4
1 3 2
"""

input = input.strip().split('\n')

n,m,s = map(int, input[0].split())
graph = [[] for _ in range(n+1)]

for i in range(1,len(input)):
    x,y,z = map(int, input[i].split())
    graph[x].append((y,z))

q = []

inf = 1e9
# <span id="받게되는-도시는-몇개이며-받는데까지-걸리는-시간"></span>받게되는 도시는 몇개이며 받는데까지 걸리는 시간

times = [inf] * (n+1)

heapq.heappush(q,(0,s))
times[s] = 0
while q:
    node,cost = heapq.heappop(q)
    if times[node] <cost:
        # 더 짧은 놈이 방문한경우가 있음.
        continue
    for n1,c1 in graph[node]:
        sum = cost + c1
        if times[n1]> sum:
            times[n1] = sum
            heapq.heappush(q,(sum , n1))
            
cnt = 0
max_v = 0

for t in times:
    if t<inf:
        cnt += 1
        if max_v<t:
            max_v = t
            
print(cnt,max_v)