23087번 - 최단최단경로
다익스트라로 최단경로 찾고
최단경로 간선만을 이용해서 bfs를 하여 최소 간선 개수 찾고
최소 간선만을 이용하여 dp로 경로의 개수를 구했는데 틀립니다. 어떤 반례가 있는지 모르겠습니다
f의 for 부분을 아래와 같이 수정하니 AC를 받았습니다. 해당 간선이 최단경로에 사용된 간선임을 확인해야하는 것 같습니다.
아 DIST만 확인해서는 최단경로에 실제로 쓰였는지 확인이 안되는군요 감사합니다 ㅠㅠ
댓글을 작성하려면 로그인해야 합니다.
p_ce1052 2년 전
다익스트라로 최단경로 찾고
최단경로 간선만을 이용해서 bfs를 하여 최소 간선 개수 찾고
최소 간선만을 이용하여 dp로 경로의 개수를 구했는데 틀립니다. 어떤 반례가 있는지 모르겠습니다