문제
정보마을 장애인 지원 단체에서는 정보마을에서 이동을 원하는 장애인의 요청이 있으면 원하는 시간에 차량을 대기시켜서 즉시 원하는 지역으로 이동시켜주는 일을 지원한다.
예산을 절약하기 위해 가능하면 최소의 차량으로 모든 요청을 지원하여야 한다. 시간대별로 이동을 원하는 요청이 모두 주어졌을 때 원하는 시간에 모든 요청을 지원하기 위해 필요한 차량의 최소 대수를 구하는 프로그램을 작성하라.
입력
서비스 요청 수 N과 정보마을 각 지점의 수 M이 차례로 주어진다. (2 <= M <= 30, 1 <= N <= 20)
둘째 줄부터 M행 M열에 걸쳐 d(i, j)가 입력되는데 i행 j열의 정수는 i지점에서 j지점으로 이동하는데 걸리는 시간을 의미한다.
서로 다른 지역으로 이동하는 시간이 0인 경우에는 직접 갈 수 있는 길이 없음을 의미한다. (0 <= d(i,j) <= 1000)
다음 줄부터 N줄에 걸쳐 각각 3개의 정수 ti, si, ei가 입력되는데 각각 i번째 요청의 시간, 출발지, 목적지를 나타낸다. (0 <= ti <= 1440, 1 <= si, ei<= M)
출력
모든 요청을 처리하기 위해 필요한 최소 차량의 대수를 출력한다.
예제
4 5
0 5 3 9 18
5 0 6 10 7
3 6 0 12 11
9 10 12 0 1
18 7 11 1 0
33 4 2
5 3 4
35 1 2
20 1 5
2
힌트
출처
2017 ICT Award KOREA
로그인해야 코드를 작성할 수 있어요.