케이스윔의 개발 블로그

문제 정의방향그래프가 주어질 때 주어진 시작점에서 다른 모든 정점으로의 최단 경로의 경로값을 구해야한다. 문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/1753) 문제 풀이다익스트라 알고리즘을 사용해서 각 정점으로의 최단 경로를 구할 수 있다. 우선 주어진 입력을 통해서 인접리스트를 만들고, 다익스트라 알고리즘을 수행하면된다. 그런데 아직 가중치가 주어진 그래프를 벡터로 표현해서 사용해본적이 없어서 벡터를 통해 인접리스트를 만들 때 가중치를 어떻게 저장해야할지 생각해보아야 한다. 가장 쉽게 생각을 하면 각 정점에서 어느 정점으로 갈지를 나타내는 수와 가중치를 함께 저장할 수 있도록 pair를 사용해봐야겠다. 인접리스트를 만든다음에는 시작점에서부터 다익스트라 알고리..