백준1 [boj-1504]특정한 최단경로 dijkstra 알고리즘을 사용하여 최단경로의 길이를 찾는 문제지만,특정 정점 두개(e1, e2)는 반드시 경유해야 함지나갔던 정점이나 간선을 다시 지나갈 수 있음이 두가지 조건이 추가된 문제였다. 시작점이 1이고 n이 도착점일 때, 이 두가지 조건을 만족하는 최단거리를 구해야 하는 것이 이 문제이다.처음에는 단순하게 문제를 3가지 작은 문제로 나누었다. 시작점 1부터 e1까지 dijkstra를 수행하여 e1까지의 최단경로를 찾음e1부터 e2까지 최단경로를 찾음. 이 때 전에 수행한 최단경로의 정보는 사용하지 않는다. 지나갔던 간선이나 정점을 다시 방문할 수 있으니까..마찬가지로 e2부터 도착점 n까지 dijkstra 수행..이렇게 했더니 당연 꽝... 빠뜨린 조건이 있나 이짓 저짓하면서 반례를 찾아보았.. 2017. 7. 31. 이전 1 다음