목록최단 경로 유발 노드 담기 (1)

Doby's Lab

[알고리즘] 백준 11780번: 플로이드 2 (C++), 최단 경로 발생 노드 담기

https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 이번 문제의 어려운 점은 아마 "i에서 j로 갈 때의 최단 경로에 속한 노드들"을 구하는 것이었다. [시도 #1] 다익스트라에서 경로 역추적했던 것을 영감 삼아 해결해보려 했었다. 3차원 동적배열을 선언하여 i와 j에 k가 들어가면서 최단 경로가 갱신될 때마다 k를 push 했다. if (graph[i][k] + graph[k][j] < graph[i][j]) { graph[i][j] = gr..
PS/BOJ 2021. 12. 6. 22:14
이전 Prev 1 Next 다음