정리충의 정리노트

0. 문제 주소 https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 www.acmicpc.net 1. 풀이 플로이드 워셜 알고리즘을 이용해서 i번 도시에서 j번 도시로 가는 최단거리가, 중간에 k번 도시를 거쳐서 가는 거리보다 클 경우 불가능, 같을 경우 i번 ~ j번을 직접적으로 잇는 도로는 필요가 없기 때문에 이를 저장해두고 순회가 끝나면 남은 도로들의 가중치만 더해주면 된다. 2. 풀이 코드 * 유의할 점 #include using namespace std; int ..