200924460   1년 전

처음에 dfs로 했다가/ 시간 초과 뜨길래 다익스트라를 공부해서 시도하였습니다. 시간 초과가 뜨더군요.

혹시. 제가 어느 블로그를 참고하여 다익스트라를 구현하였는데, 다익스트라를 잘못 구현한것인지 아니면 다익스트라 말고 다른 알고리즘을 써야하는지요.

ㅁ만약 다른 알고리즘ㅇ르 쓴다면 다익스트라가 안되는 이유는 무엇인지요.

skeksk91   1년 전

음.. 그냥 제 생각인데

먼저 x도시에서 각 도시로 최단경로를 구합니다. 이때 거리 다 저장하고.

그리고 x도시에서 각 도시로 가는 방향들의 도로를 제거합니다.

그리고 이제 각 도시에서 x로 가는 도로들의 방향을 거꾸로 해주고

x에서 다시 다익스트라를 돌리면 두번만 돌려도 되지않을까 합니다..

문제를 풀어보지 않아서 잘 모르겠지만 맞으면 좋겠습니다~


댓글을 작성하려면 로그인해야 합니다.