문제 설명
•
명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생이 누구인지 구하는 문제
◦
모든 학생은 자신의 마을에서 번 마을로 가고, 다시 그들의 마을로 돌아가야 한다.
◦
학생들은 항상 최단 경로로 왔다 갔다 한다.
◦
도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다.
예제 입력/출력
•
입력1
4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3
Plain Text
복사
•
출력1
10
Plain Text
복사
제약 조건
•
◦
: 학생의 수
•
◦
: 단방향 도로의 개수
◦
도로의 가중치
문제 풀이
•
다익스트라 알고리즘을 이용하여 해결하면 된다.
풀이 1 모든 정점 사이의 최단 거리를 구하는 풀이 -
풀이 2 로 가는 최단 거리와 에서 시작하는 최단 거리만 구하는 풀이 -
풀이 코드
풀이 1 -
풀이 2 -