출발지 start, 경유하는 정점 vertex, 도착점 end가 있을때의 최단경로를 보이고 그 합을 구하는 문제인데요,

이때 start -> vertex로 갈때는 end노드를 지나면 안되고 vertex -> end로 갈때는 start노드를 지나면 안된답니다.



간단하게 floyd 알고리즘에서 start노드와 end노드를 제하고 계산하면 되겠구나 했는데,

(만약 5 x 5 매트릭스라면 정점은 1,2,3,4,5가 있는 것이고, 여기서 모든 정점의 최단거리를 구할려면 1에서 5까지 반복문을 돌리는데,

만약 start가 2고 end가 5면  2와 5는 제하고 계산하는 방법으로 했습니다.)


반정도는 답이 나오는데 반은 답이 안나오더라고요. 중간에 제해야할 노드가 껴있어서 보니까,

최단거리를 구하기 전에, 미리 입력받은 값에 그 노드로 가는 길이 있으면 그냥 가버리더라고요.

저의 머리로는 이걸 어떻게 풀어야할지 감이 안옵니다-_-; 힌트 좀 부탁드려요..



ps. 출력할때 재귀형식으로 출력하는데, 그때 제해야할 노드를 제하면 경로의 답은 나오는데 최단거리의 합이 틀리게 나오더라고요.
     그래서 floyd 알고리즘에서 뭘 어떻게해야할꺼 같은데..

ps2. 일단 해본 방법은,

1. start -> vertex로 갈때 floyd를 쓰면서 end노드의 최단경로는 계산하지 않음, vertex -> end로 갈때 start도 마찬가지로.. (floyd 두번씀) :: 답이 안나옴
2. 위의 것에서 제한할 노드로 가는길을 막음. (즉, d[i][k]와 d[k][j]를 MAX로 둠) :: 역시 답이 안나옴;
이 게시물을...