A Great Way

면접 대비

시간 제한1초메모리 제한128 MB

요약
간선 비용이 c + d*max(0,e-10)인 그래프에서 노드 1부터 노드 N까지 최소 비용과 최소 거친 노드 수를 구합니다.
난이도

보통10점 중 5점

유형
그래프, 최단 경로, 동적 계획법
정답자
아직 제출이 없습니다

문제

정우는 대회 준비를 위해 중앙대학교에서 숭실대학교까지 가려 한다. 중앙대학교에서 숭실대학교까지 가려면 몇 개의 거점을 지나쳐야 한다. 각 거점을 경유할 때 발생하는 10분당 기본요금과 1분당 추가요금은 모두 다르다. 정우는 숭실대학교까지 가장 적은 비용을 사용해서 도착하려 한다. 중앙대학교에서 숭실대학교까지 가는 최소 비용과 거쳐야 하는 거점의 수를 구하는 프로그램을 작성하자.

입력

첫 번째 줄에 거점의 수 NN과 경로의 개수 RR이 주어진다. (2≤N≤1002 \le N \le 100, 1≤R≤2001 \le R \le 200) 모든 거점에는 1부터 NN까지 번호가 매겨져 있으며 중앙대학교는 1번, 숭실대학교는 NN번이다. 두 번째 줄부터 RR개의 줄에 걸쳐 각 경로에 대한 정보 (a,b,c,d,e)(a, b, c, d, e)가 순서대로 주어진다. aa는 시작 거점, bb는 도착 거점, cc는 기본요금, dd는 1분당 추가요금, ee는 걸리는 시간이다. (1≤a,b≤1001 \le a, b \le 100, 1≤c,d,e≤1001 \le c, d, e \le 100) 단, cc, dd, ee는 정수이다.

출력

첫 번째 줄에 최소 비용과 거쳐야 하는 거점의 수를 차례대로 출력한다. 중앙대학교부터 숭실대학교까지 도착할 방법이 없을 경우에는 'It is not a great way.'를 출력한다. 단, 최소 비용 경로가 여러 가지 존재하면 거점의 수를 최소화하여 출력해야 한다.

예제2

  1. 예제 1

    입력
    3 3
1 2 3 1 12
1 3 5 2 20
2 3 3 2 8
    예상 출력
    8 3

  2. 예제 2

    입력
    4 2
1 2 5 2 11
2 3 8 1 21
    예상 출력
    It is not a great way.