알고리즘,PS/백준
2021. 10. 2.
[BOJ] 백준 [5719] 거의 최단 경로 JAVA
https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 문제 풀이 쉽게 풀 수 있을줄 알았다 .. 최단 경로 찾아서 없애주고 , 처음 구한 최단경로보다 높은 값 나올때까지 다익스트라 다시 쓰면 되는줄 ..하지만 실패하고 반례를 살펴보니 다른 조건이 추가되어야 했다. 예를들어 , 0에서 출발하여 2로 도착하는 예시에서 최단 경로가 될 수 있는 경우의 수는 2가지이다. (0->3->2 , 0->3->1->2) 만약 0->3-..