야생가오리

https://www.acmicpc.net/problem/1389 결국 그래프에서 한 정점으로부터 다른 정점까지의 최단거리를 모두 구해서 더해주겠다는 뜻= 최단경로 알고리즘= 그중에서도 모든 정점간 최단거리를 구할 수 있는 플로이드워셜을 쓰면 된다. 플로이드-워셜은 가능한 모든 두 정점 간 조합에 대한 최단경로를 구하는 ASP(All-Pairs) 알고리즘으로, 두 정점 사이의 최단경로에 포함될 수 있는 모든 정점을 고려한다.정점 V개 간선 E개에서 O(V^3)의 복잡도를 가진다.모든 정점 사이의 최단경로를 구해야할 때는 다익스트라보다 효율적인 부분이 있다. 각 정점을 중간 정점으로 하여, 시작과 끝점에서 해당 정점을 지나는 것과 지나지 않는 것 중 더 짧은 거리를 선택해 그것을 최단경로로 한다. 중간/시..

https://www.acmicpc.net/problem/1238 문제N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.입력첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ..