Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- 네이버 인턴
- ㅁㅇㅂ??ㅇㅈㄷ ㅎㅇㅌ...
- jsp
- EER
- 행정지역 DB
- Django
- 3단계 지역 DB
- 정보보호병 후기
- mysql
- react
- 메모리 포랜식
- 인턴 후기
- spring
- frontend
- 방명록 만들기
- restapi
- 동읍면 DB
- reversing.kr
- 인턴 지원
- webhacking 처음
- DBMS
- PyAmdecoder
- 소개딩
- Database
- JSTL
- Layered Architecture
- riceteacatpanda
- Forensic 절차
- 소프트웨어 개발보안 경진대회
- SessionAttribute
Archives
- Today
- Total
웹찢남
[백준 1916 최소비용 구하기] PYTHON 본문
간단한 다익스트라 알고리즘 문제이다.
import sys
import heapq
input = sys.stdin.readline
def dijkstra(start, end):
heap = []
heapq.heappush(heap, (0, start))
distance = [sys.maxsize] * (N + 1)
distance[start] = 0
while heap:
cost, city = heapq.heappop(heap)
for e, c in bus[city]:
if distance[e] > cost + c:
distance[e] = cost + c
heapq.heappush(heap, (cost + c, e))
return distance[end]
if __name__ == "__main__":
N = int(input())
M = int(input())
bus = [[] for _ in range(N + 1)]
for _ in range(M):
a, b, c = map(int, input().split())
bus[a].append((b, c))
start, end = map(int, input().split())
print(dijkstra(start, end))
'백준 Algorithm' 카테고리의 다른 글
[백준 11726 2xn 타일링] PYTHON (0) | 2021.04.13 |
---|---|
[백준 1260 DFS와 BFS] PYTHON (0) | 2021.02.26 |
[백준 1927 최소 힙] PYTHON (0) | 2021.02.26 |
[백준 1463 1로 만들기] PYTHON (0) | 2021.02.26 |
[백준 11047 동전 0] PYTHON (0) | 2021.02.26 |
Comments