[알고리즘] 유명 알고리즘 대회

1. 문제

• 어떤 나라에 N개의 도시가 있다.
• X에서 Y로 향하는 통로가 있으면 X->Y는 보낼 수 있지만 Y->X로는 따로 통로가 있어야 한다. 
• 특정 도시에서 다른 도시로 전부 전보를 보내기 위해서 필요한 시간은 얼마인지 계산하라.

 

2. 접근

1. 하나의 도시에서 모든 도시로 전보를 보내기에 개선된 다익스트라를 사용하면 된다

2. heap을 이용해 우선순위 큐를 구현하면 된다

 

3. 풀이

# 전보는 우선순위 큐 ( 개선된 다익스트라 문제 ) 이다

import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)

n, m, start = map(int, input().split())

# 1차원 리스트 초기화
graph = [[] for _ in range(n+1)]

distance = [INF] * (n+1)

# 모든 간선 정보 입력
for _ in range(m):
    a, b, c = map(int, input().split())
    # a-> b까지 비용이 c
    graph[a].append((b, c))


def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))


dijkstra(start)

count = 0
maxDistance = 0

for d in distance:
    if d != INF:
        count += 1
        maxDistance = max(maxDistance, d)

print(count - 1, maxDistance)