경로를 구하는 법을 잘 모르겠어서 다른 풀이를 참고했다. 다음에 풀 때는 잘 풀 수 있기를 !!
- 가중치가 최대가 되는 경로를 구해야 하므로 주어진 가중치에
-1을 곱하여 최단경로 문제로 바꿀 수 있다. - 경로를 구하기 위해
prev배열을 선언하여 최단경로가 업데이트될 때마다 방문한 노드를 배열에 저장하면 된다. - 싸이클이 존재하더라도 1에서 n까지 가는 경로에 싸이클이 없으면 가능한 경로가 된다. 이를 구하기 위해 최단 경로를 구하기 전
bfs를 통해 n과 연결된 길의 방문 노드를 체크한다.
