문제 출처 : https://www.acmicpc.net/problem/1238

문제 정리

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

문제 해결 방법

딱 보자마자 플로이드 와샬을 사용하면 되겠다고 생각이 드는 문제

→ 플로이드 와샬

코드

• click

코드 설명

1. dist : 모든 단방향 간선 정보를 저장하는 2차원 배열
   • 플로이드 와샬을 사용하려면 항상 큰 수로 초기화를 시켜줘야 한다.
2. 데이터를 입력 받는 과정
3. 플로이드 와샬 알고리즘
4. 가장 많은 시간을 소비하는 학생을 구하는 과정
   1. 주의할 점은 파티를 여는 마을의 시간은 제외시켜야 한다.
   2. 파티를 여는 마을은 입력으로 주어지기 때문에 임의의 마을에서 파티를 여는 마을에 가는 시간과, 파티를 여는 마을에서 임의의 마을로 가는 시간을 더한 값을 구해야 합니다.