알고리즘/Dijkstra algorithm(데이크스트라 알고리즘)

[Python] 1504-백준-특정한 최단 경로

2023. 4. 7. 17:25
목차
  1. 1. 문제 출처
  2. 2. 풀이
  3.  

1. 문제 출처

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

 

1504번: 특정한 최단 경로

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존

www.acmicpc.net

2. 풀이

데이크스트라를  1->v1->v2->n or  1->v2->v1->n 순으로 3번 사용해야 한다. 

해당 해답은 pypy3 로 실행 하였다.

import heapq
#입력
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())

# 데이크 스트라 알고리즘
def di(start,size):
    # 사용한 길 계속 사용 가능 하므로 계속 초기화 한다.
    distance = [float('inf')] * (size+1)
    q = []
    heapq.heappush(q, [0,start])
    distance[start] = 0
    
    while q:
        dist, node = heapq.heappop(q)
        
        if distance[node] < dist:
            continue
        for n,w in graph[node]:
            cost = dist + w
            
            if distance[n] > cost:
                distance[n]= cost
                heapq.heappush(q,[cost,n])
                
    return distance

#각각 1,v1,v2가 시작점으로 각 노드에 대한 최단 경로를 담고 있다.
d1 = di(1,n)
d2 = di(v1,n)
d3 = di(v2,n)
# v1을 먼저 들리거나 v2를 먼저 들리거나 비교해서 더 짧은 거리를 사용한다.
result = min(d1[v2]+d2[n]+d3[v1],d1[v1]+d2[v2]+d3[n])


if result == float('inf'):
    print(-1)
else:
    print(result)

 

'알고리즘 > Dijkstra algorithm(데이크스트라 알고리즘)' 카테고리의 다른 글

[Python]4485-백준-녹색 옷 입은 애가 젤다지?  (0) 2023.04.13
[Python] 1238-백준-파티  (0) 2023.04.06
13549-백준-숨박꼭질3  (0) 2023.04.05
1916-백준-최소비용 구하기  (0) 2023.04.04
1753-백준-최단경로  (0) 2023.04.03
  • 1. 문제 출처
  • 2. 풀이
  •  
'알고리즘/Dijkstra algorithm(데이크스트라 알고리즘)' 카테고리의 다른 글
  • [Python]4485-백준-녹색 옷 입은 애가 젤다지?
  • [Python] 1238-백준-파티
  • 13549-백준-숨박꼭질3
  • 1916-백준-최소비용 구하기
easysheep
easysheep
easysheep
나의 개발자 일기
easysheep
전체
오늘
어제
  • 분류 전체보기 (95)
    • 파이썬 (7)
      • 자료형 (0)
      • matplotlib (2)
      • Tensorflow (1)
      • Selenium (1)
      • Numpy (2)
      • Pandas (1)
    • 장난감 프로젝트 (3)
    • AI_수학 (0)
      • 통계 (0)
    • 알고리즘 (63)
      • 브루트 포스 (3)
      • 그리드 알고리즘 (5)
      • 너비 우선 탐색(bfs) (12)
      • 깊이 우선 탐색(DFS) (1)
      • 최단 경로 구하기(플로이드 워셜) (1)
      • 동적 계획법(Dynamic Programming) (8)
      • Dijkstra algorithm(데이크스트라 알.. (6)
    • Backend (1)
      • Django (1)
    • 딥러닝 (1)
      • Regression(회귀) (0)
    • 머신러닝 (3)
      • Daycon (1)
      • 직접 구현 (1)
    • AWS (3)
    • DB (2)
      • MongoDB (2)
    • kubernetes (3)
    • Docker (4)
    • Stress Test Toll (0)
      • Jmeter (0)
      • nGrinder (0)
    • Ubuntu (3)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • error
  • ubuntu
  • validate service connection
  • 백준
  • ML
  • mysql
  • 헬름 설치
  • Python
  • BFS
  • dynamic programming
  • Cannot stat file /proc/528/fd/0: Permission denied
  • 2*n 타일링
  • error: version in "./docker-compose.yaml" is unsupported.
  • 파이썬
  • gradio
  • 우분투에 헬름 설치
  • 알고리즘
  • Docker
  • Numpy
  • aws
  • Bind Mounts
  • heap
  • 문자열
  • helm
  • 데이크스트라
  • 너비 우선 탐색
  • matplotlib
  • grafana
  • 머신 러닝
  • Mac

최근 댓글

최근 글

hELLO · Designed By 정상우.
easysheep
[Python] 1504-백준-특정한 최단 경로
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.