[파이썬] 백준 1504 : 특정한 최단 경로(골드4)

[파이썬] 백준 1504 : 특정한 최단 경로(골드4)

 

1504번: 특정한 최단 경로

---

문제

---

풀이

0. 방향성 생각

간선 정보가 주어진 그래프가 주어지고 최소비용으로 목적지에 도달해야한다.

다익스트라 활용해서 풀이

1. 입력

import heapq as hq
import sys
input = lambda : sys.stdin.readline().rstrip()

n,e = map(int,input().split())
graph = {i: {} for i in range(1,n+1)}

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

graph[시작노드][도착노드] = 간선정보가 나오게 딕셔너리 입력을 받는다.

 

2. 함수 정의

def dijkstra(start,end):
    
    global graph
    
    costs = {node: 1e9 for node in graph}
    costs[start] = 0
    
    q = []
    hq.heappush(q,[costs[start],start]) 
    
    while q:      
        cost,x = hq.heappop(q)
        
        if cost > costs[x]:
            continue
        
        for nx,ncost in graph[x].items():
            new_cost = cost + ncost
            if new_cost < costs[nx]:
                costs[nx] = new_cost
                hq.heappush(q,[new_cost,nx])
    return costs[end]

그래프의 시작, 도착점을 넣으면 최소 간선정보를 리턴하는 다익스트라 함수 작성

힙에 (cost[노드],노드) 순으로 넣어서 최소 cost부터 탐색되게 설정한다.

현재 노드에 저장된 cost와 nx로 가는 ncost = new_cost 라 했을 때, 이 값이 nx에 저장된 cost보다 작으면 업데이트하고 큐에 추가한다.

3. 출력

answer = min([dijkstra(1,v1)+dijkstra(v2,n),
              dijkstra(1,v2)+dijkstra(v1,n)]) + dijkstra(v1,v2)
print(-1) if answer >= 1e9 else print(answer)

v1,v2는 무조건 거쳐야 한다. 공통된 부분.

1 -> v1, v2 -> n

1 -> v2, v1 -> n

두 케이스 중 작은 값으로 쓴다.

1e9로 설정해도 계산해서 리턴값 반환함. flaot('inf')로 쓰는게 나을듯

1e9보다 크거나 같으면 -1, 아니면 계산한 값으로.

---

전체코드

import heapq as hq
import sys
input = lambda : sys.stdin.readline().rstrip()

n,e = map(int,input().split())
graph = {i: {} for i in range(1,n+1)}

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

def dijkstra(start,end):
    
    global graph
    
    costs = {node: 1e9 for node in graph}
    costs[start] = 0
    
    q = []
    hq.heappush(q,[costs[start],start]) 
    
    while q:      
        cost,x = hq.heappop(q)
        
        if cost > costs[x]:
            continue
        
        for nx,ncost in graph[x].items():
            new_cost = cost + ncost
            if new_cost < costs[nx]:
                costs[nx] = new_cost
                hq.heappush(q,[new_cost,nx])
    return costs[end]

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

answer = min([dijkstra(1,v1)+dijkstra(v2,n),
              dijkstra(1,v2)+dijkstra(v1,n)]) + dijkstra(v1,v2)
print(-1) if answer >= 1e9 else print(answer)