hibiscus

✔ 주의할 점 가능한 경로 2개 1 -> v1 -> v2 -> N 1 -> v2 -> v1 -> N 다익스트라 함수를 만들어 놓고, (1, v1), (v1, v2), (v2, N) (1, v2), (v2, v1), (v1, N) 각 지점 사이의 최단 경로를 구한 뒤, 두가지의 경로 중 최단 거리를 구했다! import sys # 1번 부터 N까지의 최단거리 v1, v2 거쳐서 # 경로없을 때는 1 from heapq import heappop,heappush INF = int(1e9) def dijkstra(start, end): D = [INF] * (N+1) D[start] = 0 Q = [(0, start)] while Q: d, u = heappop(Q) if D[u] < d: continue i..

다익스트라로 풀었음! 각자의 집에서 -> X번 집(생일파티집) => 각자의 집 X번 -> 각자의 집은 다익스트라 한 번 돌리면 되지만, 각자의 집에서 X번집의 최단거리들을 구하려면 여러번 돌아야 한다. 그래서 그래프를 만들때 각자의 집 -> X번 집을 쉽게 구하기 위해서 X 번집을 기준으로 두고, 각자의 집으로 가는 (반대방향) 으로 그래프를 만들어 다익스트를 2번만 돌리면 되도록 했다! from collections import deque INF = int(1e9) def dijkstra(start, graph): D = [INF] * (n + 1) D[start] = 0 Q = deque() Q.append(start) while Q: node = Q.popleft() for n_node, w in ..