문제

https://www.acmicpc.net/problem/1753

point

다익스트라

변수

• graph : 각 노드에 연결된 노드와 그 가중치 넣어준다.
• asw : 계속 update 해 줄 start 노드와 나머지 노드간의 거리다.
• pq에 넣는 rule
  • pq에 방문 할 수 있는 노드 넣는다.
  • 방문 할 수 있는 노드
    : 지금 경로로 방문하면 start와의 거리가 줄어드는 노드
    1) 처음 방문하는 노드
    2) 다시 방문하는데 이번 경로의 거리가 더 짧을 경우
  • (start와의거리, 노드번호) tuple 형태로 넣는다.
• pq 꺼내는 rule
  • 노드 정렬을 start와의 거리로 한다.
  • 탐색(방문) 할 수 있는 노드 중, 여태까지 start와의 거리가 가장 작은 경로를 가지는 노드부터 탐색한다.

구현

• pq의 초기값은 max(1e9)
• 시작 노드 pq에 push : (0,start)
• pq empty까지 반복
  • nxt = heappop(pq) : pq 중 start와의 거리 가장 작은 노드 방문
  • nxt와 인접한 노드 중 방문 가능한 노드 있으면 pq에 push
    • 방문 가능한 노드
      : 기존 경로 거리 > 현재 경로 거리
      : asw[nxt] > cur_c + nxt_c
      
• asw : start와 각 노드간 최소 거리

인접 리스트

• 인접 행렬 사용하면 메모리초과 발생

내 코드 시간복잡도 낭비

• 인접리스트에 같은 노드간 간선이 여러개인 경우 최소가중치만 넣은것이 아니라 그냥 여러개 다 넣었다.
  -> 방문 후 간선 loop 도는 회수 증가
  -> 뒤에 도는 간선이 가중치가 작을 경우, 둘 다 pq에 들어갈 수도 있다.
  -> 나중에 가중치 큰놈 pop해서 나오면 loop도는 동안 동작 아무것도 안하게 됨.

전체코드

import heapq
INF = int(1e9)

v, e = [int(x) for x in input().split()]
k = int(input())

graph = [[] for _ in range(v+1)]
for _ in range(e):
  a, b, c = [int(x) for x in input().split()]
  graph[a].append((b,c))


asw = [INF] * (v+1)
pq = []
heapq.heappush(pq,(0,k))
while pq:
  cur_c, cur_v = heapq.heappop(pq)
  for nxt_v, next_c in graph[cur_v]:
    new_c = cur_c + next_c
    if asw[nxt_v] > new_c:
      asw[nxt_v] = new_c
      heapq.heappush(pq,(new_c,nxt_v))

asw[k] = 0
for i in range(1,v+1):
  if asw[i] == INF:
    print("INF")
  else:
    print(asw[i])

다른 코드 (1이 시작점, 노드 n개)

    graph = [[]for _ in range(n+1)]    
    for a, b in edge:
        graph[a].append(b)
        graph[b].append(a)
    
    dis = [INF]*(n+1)
    dis[1] = 0
    pq = []
    heapq.heappush(pq, (0,1))
    while pq:
        cur_d, cur = heapq.heappop(pq)
        for a in graph[cur]:
            new_d = cur_d + 1
            if new_d < dis[a]:
                dis[a] = new_d
                heapq.heappush(pq, (new_d,a))