https://www.acmicpc.net/problem/11265 11265번: 끝나지 않는 파티 입력의 첫 번째 줄에는 파티장의 크기 N(5 ≤ N ≤ 500)과 서비스를 요청한 손님의 수 M(1 ≤ M ≤ 10,000) 이 주어진다. 각각의 파티장은 1번부터 N번까지 번호가 붙여져 있다. 다음에는 N개의 줄에 걸 www.acmicpc.net 최단 경로 문제다. 플로이드 워셜을 이용하여 풀었다. 이 문제의 입력은 (시작, 끝, 가중치)가 아닌 배열로 입력이 들어오기 때문에 편했다. 플로이드 워셜을 이용해 모든 지점에서 모든 지점까지의 최단 경로를 구한다. m개의 입력을 맏아 a에서 b까지 걸리는 시간이 c초과와 이하인 경우로 나눠 출력을 한다. #include using namespace std; i..
Algorithm/Shortest Path
https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드 워셜 문제다. 모든 지점에서부터 모든 지점까지의 최단 경로를 구하는 문제다. 문제 이름처럼 플로이드 워셜을 이용한다. 플로이드 워셜은 코테용이 아닌 이론부터 공부를 했다. 플로이드 워셜의 개념은 아래와 같다. dij(k)는 i에서 j까지 가는데 k이하의 수를 거쳐서 지나갔을 때의 최단 경로를 의미한다. 거쳐간다의 의미는 i 와 j를 제외한 노드의 번호다. k == 0 일 때는 아무것도 거..
