김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

백준(BOJ) 1504 특정한 최단 경로 파이썬(Python)

문제 링크

직관적인 문제이다.

  1. 다익스트라 알고리즘을 이용해 1~v1과 1~v2의 거리를 구한다. 다익스트라 알고리즘은 SSSP 알고리즘이므로 한 번 돌리면 두 값을 모두 구할 수 있다.
  2. v1~v2의 거리를 구한다. 문제의 그래프는 무향(양방향) 그래프이므로 v1~v2는 v2~v1과 같다.
  3. n~v1과 n~v2의 거리를 구한다. 마찬가지로 무향 그래프이기 대문에 n~v1(n~v2)는 v1~n(v2~n)과 같다.
  4. min(1~v1 + n~v2, 1~v2 + n~v1) + v1~v2가 문제의 답이 된다.
from sys import stdin
from heapq import *
input = stdin.readline
# 두 가지 경우가 있다
# 1-v1-v2-n
# 1-v2-v1-n

n, e = map(int, input().split())
graph = [[] for _ in range(n+1)]

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

v1, v2 = map(int, input().split())

# 다익스트라 알고리즘을 구현한 함수
# 시작점과 2개의 종료점을 받아서 각각의 거리를 튜플로 반환한다
def djk(start, end1, end2):
    distance = [float('inf')] * (n+1)
    distance[start] = 0
    q = []
    heappush(q, (start, 0))
    
    while q:
        node, cost = heappop(q)
        if distance[node] < cost:
            continue
        for nextNode, nextCost in graph[node]:
            if distance[node] + nextCost < distance[nextNode]:
                distance[nextNode] = distance[node] + nextCost
                heappush(q, (nextNode, distance[nextNode]))
    
    return distance[end1], distance[end2]

# 시작점에서 v1, v2까지의 거리
startv1, startv2 = djk(1, v1, v2)
# v1과 v2 사이의 거리
v1v2, _ = djk(v1, v2, v2)
# v1, v2에서 종료점까지의 거리
v1end, v2end = djk(n, v1, v2)

ans = min(startv1+v2end, startv2+v1end)+v1v2
print(ans if ans != float('inf') else -1)

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑