백준 10282 : 문제링크
문제유형 :
- 그래프
- 다익스트라 최단 경로 알고리즘
설명
- 정점의 개수 N, 간선의 개수 D
- 우선순위 큐를 이용하여, 시간복잡도 O(NlogD)로 해결할 수 있습니다
풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34import heapq
import sys
input = sys.stdin.readline
def dijkstra(strat):
heap_data = []
heapq.heappush(heap_data, (0, start))
distance[start] = 0
while heap_data:
dist, now = heapq.heappop(heap_data)
if distance[now] < dist:
continue
for i in adj[now]:
cost = dist + i[1]
if distance[i[0]] > cost:
distance[i[0]] = cost
heapq.heappush(heap_data, (cost, i[0]))
for _ in range(int(input())):
n, m, start = map(int, input().split())
adj = [[] for i in range(n + 1)]
distance = [1e9] * (n + 1)
for _ in range(m):
x, y, cost = map(int, input().split())
adj[y].append((x, cost))
dijkstra(start)
count = 0
max_distance = 0
for i in distance:
if i != 1e9:
count += 1
if i > max_distance:
max_distance = i
print(count, max_distance)
