spfa 썸네일형 리스트형 UVaOJ)12878 Flowery Trails 문제:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4743 그래프에서 0번 정점에서 n-1번 정점으로의 여러경로의 최단거리에 속한 간선들의 가중치의 합을 구하는 문제이다. 한 정점에서 한 정점으로의 최단거리가 유일하다면 경로의 가중치의 합을 구하는건 그렇게 어렵지 않게 풀 수 있다. 하지만 최단거리가 여러가지 경로가 있다면 다익스트라를 이용할 시 그걸 구하는 시간만해도 꽤 오랜 시간이 걸릴 수 있다. 처음 문제를 접근할 때 다익스트라를 돌리며 일일이 경로를 다 저장하여 역추적을 하여 tle를 받게되었다. 하지만 잘 생각해본다면 다익스트라(혹은 spfa) 두번의 전처리로 문제를 해.. 더보기 이전 1 다음