전보

출처:: 유명알고리즘 대회 

분류::

 

1. 문제 이해 및 해결과정

- 메세지를 보내고자 하는 도시 C가 출발점이 된다.

#input
3 2 1
1 2 4
1 3 2
#output
2 4

 

2. 풀이방법

 1.다익스트라

#전보
#
import sys
import heapq
sys.stdin = open("input.txt","r")
input=sys.stdin.readline
n,m,start=map(int,input().split())
graph=[[] for _ in range(n+1)]
INF=1e9
dist=[INF]*(n+1)
visited=[False]*(n+1)
for _ in range(m):
    x,y,z=map(int,input().split()) #x에서 y로 이어지는 통로에서 메세지 전달시간이z
    graph[x].append((y,z))

def dijkstra(start):
    dist[start]=0
    visited[start]=True
    q=[]
    heapq.heappush(q,(0,start))
    while q:
        c,cur=heapq.heappop(q)
        if dist[cur]<c:
            continue
        for i in graph[cur]:
            cost=dist[cur]+i[1]
            if dist[i[0]]>cost:
                dist[i[0]]=cost
                heapq.heappush(q,(cost,i[0]))

dijkstra(start)
print(dist)
cnt=0
sol=0
for d in dist:
    if d!=INF:
        cnt+=1
        sol=max(sol,d)
print('%d %d' %(cnt-1,sol)) #시작노드 제외해야하므로 cnt-1

 

3. 오답원인

 

4. 알게된 점