1. 구현까지 되어있다면 코드도 같이 올리는 것이 좋을 것 같습니다.
2. 제가 이해한 것에 따르면 1->i의 최단경로를 찾고, 그 최단경로 위의 간선을 모두 없앤 뒤 최단거리를 구하는 방식인 것 같은데,
같은 도시를 지날 수 없기 때문에, 1->i의 경로가 i->1에 영향을 주기 때문에 최단거리가 보장이 안됩니다.
예를 들어,
3 3
1 2 3 4
2 3 0 0
1 3 10 100
과 같은 입력이 들어오는 경우, 3을 지나는 경로를 계산할 때는 1->2->3 거리 3, 3->1 거리 100으로 구해지기 때문에 문제가 있습니다.
shin8469 7년 전
다시 돌아오는것까지 최소값 구하는 거라서
일단 다익스트라 알고리즘으로 각점에 최소값을 구하고
dist[i] 즉 최소값과 1이 가는곳에 weight와 같으면 다른 방을 거치지 않았다고 생각하기 때문에
그 weight를 지우고 다익스트라를 돌려서 최소 값을 바꿔줍니다
그 지운 weight를 다시 추가하고 또 같은 점이 있으면 마찬가지로 지운다음에 dist 값을 바꿔주고 이런 작업을 계속 반복한후에 마지막에
1로 돌아가는 weight를 더해주고 그 최소값을 출력합니다
예제문도 돌리고 다른것도 계속 돌려봣는데 다 됫는데 제 알고리즘 자체에 무슨 오류가 있는건가요???