플루이드 워샬1 [백준, 1956, G4] 운동 0. 문제 링크 https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 1. 문제 핵심 일방 통행 도로로 이루어진 V개 마을과 E개 도로로 구성된 도시가 있다. 사이클이 형성된 최소 도로를 찾아야 한다. 2. 문제 접근 처음에는 MST로 간선치가 작은 선분부터 집어넣고 사이클이 형성되었으면 BFS로 최소 경로 비용을 찾기로 했습니다. 하지만 역시 시간 초과, 메모리 초과로 해결할 수 없었습니다. 질문 확인 결과 사이클.. 2022. 10. 20. 이전 1 다음