shin8469   7년 전

다시 돌아오는것까지 최소값 구하는 거라서

일단 다익스트라 알고리즘으로 각점에 최소값을 구하고

dist[i] 즉 최소값과 1이 가는곳에 weight와 같으면 다른 방을 거치지 않았다고 생각하기 때문에

그 weight를 지우고 다익스트라를 돌려서 최소 값을 바꿔줍니다

그 지운 weight를 다시 추가하고 또 같은 점이 있으면 마찬가지로 지운다음에 dist 값을 바꿔주고  이런 작업을 계속 반복한후에 마지막에

1로 돌아가는 weight를 더해주고 그 최소값을 출력합니다

예제문도 돌리고 다른것도 계속 돌려봣는데 다 됫는데 제 알고리즘 자체에 무슨 오류가 있는건가요???


zlzmsrhak   7년 전

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년 전

일단 c와 d는 1이상으로 들어가야한다고 문제에 나와있는데요

제 소스보시고 안되는 경우가 어떤 건지 알려주실수 있나요 ㅠㅠ

zlzmsrhak   7년 전

랜덤으로 생성한 반례입니다.

shin8469   7년 전

INF 값 범위 문제였던거 같네요 시간초과 뜨네요 감사요 ㅎ

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