최단 경로 알고리즘 예제: 전보

도시가 n개 있고 통로가 m개 있다.

c도시에서 메세지를 보낼 건데,

총 몇 개의 도시에 메세지를 보낼 수 있으며

메세지가 도달하는데 걸릴 시간은 어떻게 되겠는가?

---

노드개수n, 간선개수m, 출발지점 c를 입력받고

c에서 출발하는 모든 최단거리를 계산하고,

최단거리가 INF가 아닌 값들의 개수, 최단거리 중 가장 큰 값을 찾아 출력하면 된다

import sys, heapq
input=sys.stdin.readline

INF=int(1e9)
n,m,c=map(int,input().split()) #노드개수 n, 간선개수 m, 출발지점c

graph=[[]for i in range(n+1)] #노드 연결정보를 저장할 그래프
for i in range(m):
    x,y,z=map(int,input().split())
    graph[x].append((y,z)) #x에서 y로 가는 비용 z

distance=[INF]*(n+1)

def dijkstra(start):
    distance[start]=0 #자기자신까지의 거리 0
    queue=[]
    heapq.heappush(queue,(0,start))
    while queue:
        dist,now=heapq.heappop(queue)
        if dist > distance[now]:
            continue
        for i in graph[now]:
            cost=dist+i[1]
            if cost < distance[i[0]]:
                distance[i[0]]=cost
                heapq.heappush(queue,(cost,i[0]))
dijkstra(c)

count=0
result=0
for i in range(1,n+1):
    if distance[i]!=INF and distance[i]!=0:
        count+=1
        result=max(result,distance[i])

print(count,result)