문제

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

# 16167
import sys
input = lambda : sys.stdin.readline().strip()
INF = sys.maxsize

n, r = map(int, input().split())
graph = [[INF] * (n+1) for _ in range(n+1)]
root = [[[i] for i in range(n+1)] for _ in range(n+1)]

for _ in range(r):
    a, b, c, d, e = map(int, input().split())
    if e >= 10:
        graph[a][b] = min(graph[a][b], c + d * (e-10))
    else:
        graph[a][b] = min(graph[a][b], c)
        
for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            if graph[a][k] + graph[k][b] < graph[a][b]:
                graph[a][b] = graph[a][k] + graph[k][b]
                root[a][b] = root[a][k] + root[k][b]
                
if graph[1][n] >= INF:
    print("It is not a great way.")
else:
    print(graph[1][n], len(root[1][n]) + 1)

백준 16167 A Great way