# BOJ - 16167 - A Great Way

Updated:

``````import sys
from collections import deque

def BFS(result, graph, N):
dq = deque()
dq.append(1)

while dq:
current = dq.popleft()
for i in range(len(graph[current])):
neigh = graph[current][i][0]
neighDist = graph[current][i][1]

if result[neigh][0] == result[current][0] + neighDist:
if result[neigh][1] > result[current][1] + 1:
result[neigh][1] = result[current][1] + 1
dq.append(neigh)

if result[neigh][0] > result[current][0] + neighDist:
result[neigh][0] = result[current][0] + neighDist
result[neigh][1] = result[current][1] + 1
dq.append(neigh)

def solution():
graph = [[] for _ in range(N+1)]
for _ in range(R):
a, b, c, d, e = map(int, sys.stdin.readline().split())
if e > 10: c += ((e - 10) * d)
graph[a].append((b, c))

result = [[1e9, 1e9] for _ in range(N+1)]
result[1][0] = 0
result[1][1] = 1
BFS(result, graph, N)

if result[N][0] == 1e9: print("It is not a great way.")
else: print(result[N][0], result[N][1])

solution()
``````

https://www.acmicpc.net/problem/16167

Categories:

Updated: