유령이 나오는 젤리하우스

Algorithm/Baekjoon

[BOJ 1753][백준 1753번] 최단 경로 (파이썬 풀이)

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 🤔 문제 설명 및 입출력 ✍ 접근 방법 1. 그래프를 탐색해야한다. 2. 근데 edge에 (음수가 아닌) 가중치가 붙어있다. 3. 다익스트라 알고리즘으로 푼다! 라는 사고방식이 머리 속 깊이 박혀 있었기 때문에, 다익스트라를 통한 풀이법을 생각하는 것은 어렵지 않습니다. 다만 "이것을 어떻게 최적화 할까?" 라는 물음에 답하는 것이 어려웠지요. 입력값이 1