백준/Platinum10 [BOJ] 5719 : 거의 최단 경로 문제 링크 5719번: 거의 최단 경로 (acmicpc.net) 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 풀이 최단경로로 통하는 길을 모두 제외한 나머지 경로 중에서 갈 수 있는 최단경로를 구하는 문제. 1. 최단경로에 포함되는 정점을 제거하면 길이 있어도 못가기 때문에 안됨 2. 최단경로를 탐색하고 도로를 바로 제거하면 만약 최단경로가 여러개이면서 최단경로끼리 같은 도로를 공유한다면?? 두번째 최단경로는 탐색할 수 없다. => 그래서 내가 떠올린 아이디어는 탐색한 최단경.. 2022. 1. 27. 이전 1 2 다음