[백준] 1238번: 파티
https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 풀이 출발지와 목적지 사이의 최단 왕복 시간을 구하는 전형적인 최단 경로 문제이다. 다만 한 정점에서만 출발하는 것이 아니라, N개의 정점 각각에서 출발했을 때의 최단 경로를 구하고, 그중에서 최대 값을 뽑아야 한다. 처음엔 문제를 대충 읽고, 단지 모든 정점에서의 최단 경로를 구해야한다는점 만을 고려해 플로이드 워셜 알고리즘으로 접근했다. import sys N, ..
2022. 3. 26.
