Problem:


青春の片道切符

太郎君は夏休みに電車で長旅をする計画を立てています。しかし高校生の身である太郎君が一ヵ月しかない夏休みで可能な限り遠くに旅をするには、出来るだけ安い行き方と出来るだけ早い行き方をそれぞれ見つけなければうまく計画が立てられません。太郎君が素敵な旅を満喫できるように、太郎君の計画の助けになるプログラムを作ってあげましょう。

線路の情報、駅の数を入力とし、問い合わせに応じて、最小金額または最短時間を出力するプログラムを作成してください。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロふたつの行で示されます。各データセットは以下の形式で与えられます。

n m
a1 b1 cost1 time1
a2 b2 cost2 time2
:
an bn costn timen
k
p1 q1 r1
p2 q2 r2
:
pk qk rk

1 行目に線路の情報の数 n (1 ≤ n ≤ 3000)と駅の数 m (1 ≤ m ≤ 100) が与えられます。

続く n 行に i 番目の路線の情報が与えられます。各路線の情報として、路線がつなぐ２つの駅の番号 ai, bi (1 ≤ ai, bi ≤ m)、料金 costi (1 ≤ costi ≤ 1000)、移動時間 timei (1 ≤ timei ≤ 1000) が与えられます。ただし、各駅は 1 から m まで順番に番号が付けられているものとします。
なお、ai と bi が線路でつながっていれば、ai から bi、 bi からai の両方の移動が同じ料金と時間で可能とします。

続く行に問い合わせの数 k (1 ≤ k ≤ 200) が与えられます。続く k 行に i 番目の問い合わせが与えられます。各問合わせとして、出発駅 pi 、到着駅 qi 、出力する値の種類 ri (0 または 1)が与えられます。なお、問い合わせには必ず経路があるものとします。

データセットの数は 50 を超えない。

Output

データセットごとに、最小金額もしくは最短時間を１行に出力します。ri が 0 の時は最小金額を、 1 の時は最短時間を出力します。

Sample Input

6 5
1 2 200 10
1 4 400 15
1 3 250 25
2 4 100 10
4 5 150 20
3 5 300 20
2
1 5 0
1 5 1
0 0

Output for the Sample Input

450
35



Sample input:
6 5
1 2 200 10
1 4 400 15
1 3 250 25
2 4 100 10
4 5 150 20
3 5 300 20
2
1 5 0
1 5 1
0 0


Sample output:
450
35

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
def MakeRouteList(ite,start,end):
    '''make all routes list from start to end station'''
    ite.sort()
    
    output = []
    #
    for k in range(len(ite)):
        # from start
        route = []
        if ite[k][0]==start:
            route = [ite[k]]
            output.append(route)
    #       
    for j in range(len(output)):
        for k in range(len(ite)):
            if output[j][-1][1] == ite[k][0]:
                output[j].append(ite[k])
    for k in range(len(output)):
        output[k].append(0)
        output[k].append(0)
    for j in range(len(output[k])-2):
        output[k][-2] += output[k][j][2] # cost
        output[k][-1] += output[k][j][3] # time

    return output

def MinMoney(output):
    cost_temp = []
    for k in range(len(output)):
        cost_temp.append(output[k][-2])
    return min(cost_temp)
    
def MinTime(output):
    time_temp = []
    for k in range(len(output)):
        time_temp.append(output[k][-1])
    return min(time_temp)

while True:
    # n = senro_num; m = station_num
    try:
        n,m = map(int,raw_input().split())
    except EOFError:
        break
    senro_list = []
    for j in range(n):
        senro = map(int,raw_input().split())
        senro_list.append(senro)
    
    # toiawase_num
    k = int(raw_input()) 
    toiawase_list=[]
    for jj in range(k):
        toiawase = map(int,raw_input().split())
        toiawase_list.append(toiawase)
    
    for p,q,r in toiawase_list:
        route = MakeRouteList(senro_list,p,q)
        if r == 0:
            print MinMoney(route)
        elif r == 1:
            print MinTime(route)            
    
    zero = map(int,raw_input().split())
    if zero == [0,0]:
        break

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
def MakeRouteList(ite,start,end):
    '''make all routes list from start to end station'''
    ite.sort()
    
    output = []
    # 1個め
    for k in range(len(ite)):
        # from start
        route = []
        if ite[k][0]==start:
            route = [ite[k]]
            output.append(route)
    # 2個め以降        
    for j in range(len(output)):
        for k in range(len(ite)):
            if output[j][-1][1] == ite[k][0]:
                output[j].append(ite[k])
    '''output = [[(1, 2, 200, 10), (2, 4, 100, 10), (4, 5, 150, 20)],
    [(1, 3, 250, 25), (3, 5, 300, 20)],[(1, 4, 400, 15), (4, 5, 150, 20)]]'''
    for k in range(len(output)):
        output[k].append(0)
        output[k].append(0)
        for j in range(len(output[k])-2):
            output[k][-2] += output[k][j][2] # cost
            output[k][-1] += output[k][j][3] # time
    """output = [[[1, 2, 200, 10], [2, 4, 100, 10], [4, 5, 150, 20], 450, 40],
 [[1, 3, 250, 25], [3, 5, 300, 20], 550, 45],
 [[1, 4, 400, 15], [4, 5, 150, 20], 550, 35]]
"""
    return output

def MinMoney(output):
    cost_temp = []
    for k in range(len(output)):
        cost_temp.append(output[k][-2])
    return min(cost_temp)
    
def MinTime(output):
    time_temp = []
    for k in range(len(output)):
        time_temp.append(output[k][-1])
    return min(time_temp)

while True:
    # n = senro_num; m = station_num
    try:
        n,m = map(int,raw_input().split())
    except EOFError:
        break
    senro_list = []
    for j in range(n):
        senro = map(int,raw_input().split())
        senro_list.append(senro)
    
    # toiawase_num
    k = int(raw_input()) 
    toiawase_list=[]
    for jj in range(k):
        toiawase = map(int,raw_input().split())
        toiawase_list.append(toiawase)
    
    
    for p,q,r in toiawase_list:
        route = MakeRouteList(senro_list,p,q)
        if r == 0:
            print MinMoney(route)
        elif r == 1:
            print MinTime(route)            
    
    zero = map(int,raw_input().split())
    if zero == [0,0]:
        break

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
def MakeRouteList(ite,start,end):
    '''make all routes list from start to end station'''
    ite.sort()
    
    output = []
    # 1個め
    for k in range(len(ite)):
        # from start
        route = []
        if ite[k][0]==start:
            route = [ite[k]]
            output.append(route)
    # 2個め以降        
    for j in range(len(output)):
        for k in range(len(ite)):
            if output[j][-1][1] == ite[k][0]:
                output[j].append(ite[k])
    '''output = [[(1, 2, 200, 10), (2, 4, 100, 10), (4, 5, 150, 20)],
    [(1, 3, 250, 25), (3, 5, 300, 20)],[(1, 4, 400, 15), (4, 5, 150, 20)]]'''
    for k in range(len(output)):
        output[k].append(0)
        output[k].append(0)
        for j in range(len(output[k])-2):
            output[k][-2] += output[k][j][2] # cost
            output[k][-1] += output[k][j][3] # timee
    """output = [[[1, 2, 200, 10], [2, 4, 100, 10], [4, 5, 150, 20], 450, 40],
 [[1, 3, 250, 25], [3, 5, 300, 20], 550, 45],
 [[1, 4, 400, 15], [4, 5, 150, 20], 550, 35]]
"""
    return output

def MinMoney(output):
    cost_temp = []
    for k in range(len(output)):
        cost_temp.append(output[k][-2])
    return min(cost_temp)
    
def MinTime(output):
    time_temp = []
    for k in range(len(output)):
        time_temp.append(output[k][-1])
    return min(time_temp)

while True:
    # n = senro_num; m = station_num
    try:
        n,m = map(int,raw_input().split())
    except EOFError:
        break
    senro_list = []
    for j in range(n):
        senro = map(int,raw_input().split())
        senro_list.append(senro)
    
    # toiawase_num
    k = int(raw_input()) 
    toiawase_list=[]
    for jj in range(k):
        toiawase = map(int,raw_input().split())
        toiawase_list.append(toiawase)
    
    
    for p,q,r in toiawase_list:
        route = MakeRouteList(senro_list,p,q)
        if r == 0:
            print MinMoney(route)
        elif r == 1:
            print MinTime(route)            
    
    zero = map(int,raw_input().split())
    if zero == [0,0]:
        break

Submission status: Runtime Error

Solution code:
import sys

def dijkstra(m, start, goal, matrix):
  defnode = [False] * (m+1)
  cost = [sys.maxint] * (m+1)
  cost[start] = 0
  node = start
  while True:
    defnode[node] = True
    minnode = sys.maxint
    mincost = sys.maxint
    for i in xrange(1, m+1):
      if defnode[i]:
        continue
      if matrix[node][i] == sys.maxint:
        continue
      cost[i] = min(cost[i], cost[node]+matrix[node][i])
      if cost[i] < mincost:
        minnode = i
        mincost = cost[i]
    if minnode == goal:
      print cost[goal]
      return
    node = minnode

while True:
  n, m = map(int, raw_input().split())
  if n == 0 and m == 0:
    break
  cost = [[sys.maxint] * (m+1) for j in xrange(m+1)]
  time = [[sys.maxint] * (m+1) for j in xrange(m+1)]
  for i in xrange(n):
    a, b, c, t = map(int, raw_input().split())
    cost[a][b] = c
    cost[b][a] = c
    time[a][b] = t
    time[b][a] = t
  k = int(raw_input())
  for i in xrange(k):
    p, q, r = map(int, raw_input().split())
    if r == 0:
      dijkstra(m, p, q, cost)
    else:
      dijkstra(m, p, q, time)

Submission status: Runtime Error

Solution code:
# coding: utf-8
import queue

class Route:
    def __init__(self, station_number, price, time):
        self.station_number = station_number
        self.price = price
        self.time = time

class Station:
    def __init__(self):
        self.routes = []
    def addRoute(self,route):
        self.routes.append(route)

class Path:
    def __init__(self, now_station, next_station, price, time):
        self.now_station = now_station
        self.next_station = next_station
        self.price = price
        self.time = time

def search_path(stations, come_from, go_to, search_type):
    result = []
    q = queue.Queue()
    for distination in stations[come_from].routes:
        new_path = Path(come_from, distination.station_number, distination.price, distination.time)
        q.put(new_path)
    while not q.empty():
        path = q.get()
        if path.next_station == go_to:
            r = path.price if search_type == 0 else path.time
            result.append(r)
        for distination in stations[path.next_station].routes:
            update_price = path.price + distination.price
            update_time = path.time + distination.time
            next_path = Path(path.next_station, distination.station_number, update_price, update_time)
            q.put(next_path)
    print(sorted(result)[0])

route_count, station_count = map(int, input().split(" "))
stations = [Station() for i in range(station_count)]
for read_line in range(route_count):
    come_from, go_to, price, time = map(int, input().split(" "))
    route = Route(go_to - 1, price, time)
    stations[come_from - 1].addRoute(route)
search_count = int(input())
for read_line in range(search_count):
    come_from, go_to, search_type = map(int, input().split())
    search_path(stations, come_from - 1, go_to - 1, search_type)

Submission status: Runtime Error

Solution code:
# coding: utf-8
class Route:
    def __init__(self, station_number, price, time):
        self.station_number = station_number
        self.price = price
        self.time = time

class Station:
    def __init__(self):
        self.routes = []
    def addRoute(self,route):
        self.routes.append(route)

class Path:
    def __init__(self, now_station, next_station, price, time):
        self.now_station = now_station
        self.next_station = next_station
        self.price = price
        self.time = time

def search_path(stations, come_from, go_to, search_type):
    result = []
    q = []
    for distination in stations[come_from].routes:
        new_path = Path(come_from, distination.station_number, distination.price, distination.time)
        q.append(new_path)
    while len(q) > 0:
        path = q.pop(0)
        if path.next_station == go_to:
            r = path.price if search_type == 0 else path.time
            result.append(r)
        for distination in stations[path.next_station].routes:
            update_price = path.price + distination.price
            update_time = path.time + distination.time
            next_path = Path(path.next_station, distination.station_number, update_price, update_time)
            q.append(next_path)
    print(sorted(result)[0])

route_count, station_count = map(int, input().split(" "))
stations = [Station() for i in range(station_count)]
for read_line in range(route_count):
    come_from, go_to, price, time = map(int, input().split(" "))
    route = Route(go_to - 1, price, time)
    stations[come_from - 1].addRoute(route)
search_count = int(input())
for read_line in range(search_count):
    come_from, go_to, search_type = map(int, input().split())
    search_path(stations, come_from - 1, go_to - 1, search_type)

Submission status: Runtime Error

Solution code:
# coding: utf-8
class Route:
    def __init__(self, next_station, need_price, need_time):
        self.next_station = next_station
        self.need_price = need_price
        self.need_time = need_time

class Station:
    def __init__(self):
        self.routes = []
    def addRoute(self,route):
        self.routes.append(route)

class Status:
    def __init__(self, now_station, use_price, use_time):
        self.now_station = now_station
        self.use_price = use_price
        self.use_time = use_time

def search(stations, start, end, search_type):
    result = []
    queue = []
    for route in stations[start].routes:
        queue.append(Status(route.next_station, route.need_price, route.need_time))
    while len(queue) > 0:
        status = queue.pop(0)
        if status.now_station == end:
            r = status.use_price if search_type == 0 else status.use_time
            result.append(r)
        for route in stations[status.now_station].routes:
            update_price = route.need_price + status.use_price
            update_time = route.need_time + status.use_time
            queue.append(Status(route.next_station, update_price, update_time))
    print(sorted(result)[0])

route_count, station_count = map(int, input().split(" "))
stations = [Station() for station in range(station_count)]
for count in range(route_count):
    now_station, next_station, need_price, need_time = map(int, input().split(" "))
    stations[now_station - 1].addRoute(Route(next_station - 1, need_price, need_time))
search_count = int(input())
for count in range(search_count):
    start, end, search_type = map(int, input().split(" "))
    search(stations, start - 1, end - 1, search_type)

Submission status: Runtime Error

Solution code:
import queue
 
def Dijkstra_mode(vertex,edges,start,end,mode):
    weight = [0 if i==start else float("inf") for i in range(vertex)]
    Q = queue.PriorityQueue()
    Q.put((weight[start],start))
 
    while(not Q.empty()):
        cur = Q.get()
        if weight[cur[1]] < cur[0]:
            continue
        if mode == 0:
            for j in range(len(edges[cur[1]])):
                if weight[edges[cur[1]][j][1]] > weight[cur[1]] + edges[cur[1]][j][2]:
                    weight[edges[cur[1]][j][1]] = weight[cur[1]] + edges[cur[1]][j][2]
                    Q.put((weight[edges[cur[1]][j][1]],edges[cur[1]][j][1]))
        else:
            for j in range(len(edges[cur[1]])):
                if weight[edges[cur[1]][j][1]] > weight[cur[1]] + edges[cur[1]][j][3]:
                    weight[edges[cur[1]][j][1]] = weight[cur[1]] + edges[cur[1]][j][3]
                    Q.put((weight[edges[cur[1]][j][1]],edges[cur[1]][j][1]))
        if weight[end] != float("inf"):
            return weight[end]
    return weight

n,m = map(int,input().split())
edges = [[] for i in range(m)]
for i in range(n):
    data = list(map(input().split()))
    data_b = [data[1],data[0],data[2],data[3]]
    edges[data[0]].append(data)
    edges[data_b[0]].append(data_b)
k = int(input())
for i in range(k):
    p,q,r = map(int,input().split())
    ans = Dijkstra_mode(m,edges,p,q,r)
    print(ans)

Submission status: Runtime Error

Solution code:
import queue
 
def Dijkstra_mode(vertex,edges,start,end,mode):
    weight = [0 if i==start else float("inf") for i in range(vertex)]
    Q = queue.PriorityQueue()
    Q.put((weight[start],start))
 
    while(not Q.empty()):
        cur = Q.get()
        if weight[cur[1]] < cur[0]:
            continue
        if mode == 0:
            for j in range(len(edges[cur[1]])):
                if weight[edges[cur[1]][j][1]] > weight[cur[1]] + edges[cur[1]][j][2]:
                    weight[edges[cur[1]][j][1]] = weight[cur[1]] + edges[cur[1]][j][2]
                    Q.put((weight[edges[cur[1]][j][1]],edges[cur[1]][j][1]))
        else:
            for j in range(len(edges[cur[1]])):
                if weight[edges[cur[1]][j][1]] > weight[cur[1]] + edges[cur[1]][j][3]:
                    weight[edges[cur[1]][j][1]] = weight[cur[1]] + edges[cur[1]][j][3]
                    Q.put((weight[edges[cur[1]][j][1]],edges[cur[1]][j][1]))
        if weight[end] != float("inf"):
            return weight[end]
    return weight

n,m = map(int,input().split())
edges = [[] for i in range(m+1)]
for i in range(n):
    data = list(map(input().split()))
    data_b = [data[1],data[0],data[2],data[3]]
    edges[data[0]].append(data)
    edges[data_b[0]].append(data_b)
k = int(input())
for i in range(k):
    p,q,r = map(int,input().split())
    ans = Dijkstra_mode(m,edges,p,q,r)
    print(ans)

Submission status: Runtime Error

Solution code:
n,m = map(int,raw_input().split()) #n = the number of lines, m = the numer of stations

err = 100000

drcs = [] #the seq of direct route and cost
drts = [] #the seq of direct route and time

for i in xrange(n):
    a,b,cost,time = map(int,raw_input().split())
    a,b = a-1,b-1
    drcs.append((a,b,cost))
    drts.append((a,b,time))

rcs = [[0 if i==j else err for j in xrange(m)] for i in xrange(m)] #the seq from route to cost
rts = [[0 if i==j else err for j in xrange(m)] for i in xrange(m)] #the seq from route to time

while len(drcs) != 0:
    (a,b,cost) = drcs.pop()
    for i in xrange(m):
        for j in xrange(m):
            rcs[i][j] = min(rcs[i][j],rcs[i][a]+cost+rcs[b][j],rcs[i][b]+cost+rcs[a][j])

while len(drts) != 0:
    (a,b,time) = drts.pop()
    for i in xrange(m):
        for j in xrange(m):
            rts[i][j] = min(rts[i][j],rts[i][a]+time+rts[b][j],rts[i][b]+time+rts[a][j])

k = int(raw_input())
for k in xrange(k):
    p,q,r = map(int,raw_input().split())
    p,q = p-1,q-1
    if r == 0:
        print rcs[p][q]
    elif r == 1:
        print rts[p][q]
    else:
        raise "??"

gomi = raw_input()
if gomi != "0 0":
    raise "?????"

Submission status: Runtime Error

Solution code:
6 5
1 2 200 10
1 4 400 15
1 3 250 25
2 4 100 10
4 5 150 20
3 5 300 20
2
1 5 0
1 5 1
0 0

Submission status: Runtime Error

Solution code:

import numpy
INF = 1000000000

def dj(s, e, r):
  d = [INF] * 100
  done = [0] * 100
  d[s] = 0
  while True:
    v = -1
    for i in range(V):
      if not done[i] and (v == -1 or d[i] < d[v]):
        v = i
    if v == e:
      return d[e]
    done[v] = True
    for i in range(V):
      d[i] = min(d[i], d[v] + cost[v][i][r])

while True:
  cost = numpy.array([[[INF for k in range(2)] for j in range(100)] for i in range(100)])
  E, V = map(int, raw_input().split())
  if not E:
    break
  for i in range(E):
    a, b, c, d = map(int, raw_input().split())
    a -= 1
    b -= 1
    cost[a][b][0] = cost[b][a][0] = c
    cost[a][b][1] = cost[b][a][1] = d
  k = input()
  for i in range(k):
    p, q, r = map(int, raw_input().split())
    p -= 1
    q -= 1
    print dj(p, q, r)

Submission status: Runtime Error

Solution code:
import sys
import math
def subsolve(ofs,range,array,data,dofs,mode,target):
	ret = []
	if range == 0:
		if data[ofs][array[0]][mode] == -1:
			return []
		ref = dofs+data[ofs][array[i]][mode]
		ret.append(ref)
		return ret
	for i in xrange(range):
		if data[ofs][array[i]][mode] == -1:
			continue
		ref = dofs+data[ofs][array[i]][mode]
		if array[i] == target - 1:
			ret.append(ref)
			return ret
		ar = list(array)
		ar.remove(ofs)
		ap = subsolve(array[i],range-1,ar,data,ref,mode,target)
		ret.extend(ap)
	return ret
def solve():
	first = map(int,sys.stdin.readline().split())
	station = [[] for _ in xrange(first[1])]
	for i in xrange(first[1]):
		station[i] = [[] for _ in xrange(first[1])]
		for j in xrange(first[1]):
			station[i][j]=[-1,-1]
	for line in xrange(first[0]):
		linedat = map(int,sys.stdin.readline().split())
		station[linedat[0]-1][linedat[1]-1] = [linedat[2],linedat[3]]
	order = int(sys.stdin.readline())
	for i in xrange(order):
		od = map(int,sys.stdin.readline().split())
		#main loop
		print min(subsolve(0,first[1],range(first[1]),station,0,od[2],od[1]))
		
solve()

Submission status: Runtime Error

Solution code:
import sys
import math
def subsolve(ofs,range,array,data,dofs,mode,target):
	ret = []
	if range == 0:
		if data[ofs][array[0]][mode] == -1:
			return []
		ref = dofs+data[ofs][array[i]][mode]
		ret.append(ref)
		return ret
	for i in xrange(range):
		if data[ofs][array[i]][mode] == -1:
			continue
		ref = dofs+data[ofs][array[i]][mode]
		if array[i] == target - 1:
			ret.append(ref)
			return ret
		ar = list(array)
		ar.remove(ofs)
		ap = subsolve(array[i],range-1,ar,data,ref,mode,target)
		ret.extend(ap)
	return ret
def solve():
	while True:
		first = map(int,sys.stdin.readline().split())
		if not first[0]:
			break;
		station = [[] for _ in xrange(first[1])]
		for i in xrange(first[1]):
			station[i] = [[] for _ in xrange(first[1])]
			for j in xrange(first[1]):
				station[i][j]=[-1,-1]
		for line in xrange(first[0]):
			linedat = map(int,sys.stdin.readline().split())
			station[linedat[0]-1][linedat[1]-1] = [linedat[2],linedat[3]]
		order = int(sys.stdin.readline())
		for i in xrange(order):
			od = map(int,sys.stdin.readline().split())
			#main loop
			print min(subsolve(0,first[1],range(first[1]),station,0,od[2],od[1]))
		
solve()

Submission status: Runtime Error

Solution code:
cost_ans = []
time_ans = []

def set_ans(cost , time):
    cost_ans.append(cost)
    time_ans.append(time)

class Sta(object):
    """station"""
    def __init__(self, station_name):
        super(Sta, self).__init__()
        self.station_name = station_name
        self.route = []

    def add_route(self, route):
        self.route.append(route)



class Route(object):
    """route"""
    def __init__(self, cost, time, next_station):
        super(Route, self).__init__()
        self.time = time
        self.cost = cost
        self.next_station = next_station

def search_route(now_station, gool_station, cost, time):
    """search route"""

    if now_station.station_name == gool_station.station_name:
        set_ans(cost, time)
        return

    elif len(now_station.route) == 0:
        return

    for r in now_station.route:
        search_route(
                r.next_station,
                gool_station,
                cost + r.cost,
                time + r.time)
def main():

    while True:
        cost_ans = []
        time_ans = []

        n,m = map(int, raw_input().split())
        if n == 0 and m == 0:
            return

        stations = [Sta(x) for x in xrange(1,m+1) ]

        for i in xrange(n):
            a, b, cost, time = map(int, raw_input().split())
            tmp = Route(cost, time, stations[b-1])
            stations[a-1].add_route(tmp)

        k = input()
        for i in xrange(k):
            p, q, r = map(int, raw_input().split())
            search_route(stations[p-1], stations[q-1], 0, 0)
            if r == 0:
                print(min(cost_ans))
            else:
                print(min(time_ans))



if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
cost_ans = []
time_ans = []

def set_ans(cost , time):
    cost_ans.append(cost)
    time_ans.append(time)

def reset_ans():
    global cost_ans
    global time_ans
    cost_ans = []
    time_ans = []

class Sta(object):
    """station"""
    def __init__(self, station_name):
        super(Sta, self).__init__()
        self.station_name = station_name
        self.route = []

    def add_route(self, route):
        self.route.append(route)



class Route(object):
    """route"""
    def __init__(self, cost, time, next_station):
        super(Route, self).__init__()
        self.time = time
        self.cost = cost
        self.next_station = next_station

def search_route(now_station, gool_station, cost, time):
    """search route"""

    if now_station.station_name == gool_station.station_name:
        set_ans(cost, time)
        return

    elif len(now_station.route) == 0:
        return

    for r in now_station.route:
        search_route(
                r.next_station,
                gool_station,
                cost + r.cost,
                time + r.time)
def main():

    while True:
        reset_ans([],[])
        n,m = map(int, raw_input().split())
        if n == 0 and m == 0:
            return

        stations = [Sta(x) for x in xrange(1,m+1) ]

        for i in xrange(n):
            a, b, cost, time = map(int, raw_input().split())
            tmp = Route(cost, time, stations[b-1])
            stations[a-1].add_route(tmp)

        k = input()
        for i in xrange(k):
            p, q, r = map(int, raw_input().split())
            search_route(stations[p-1], stations[q-1], 0, 0)
            if r == 0:
                print(min(cost_ans))
            else:
                print(min(time_ans))



if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
cost_ans = []
time_ans = []

def set_ans(cost , time):
    cost_ans.append(cost)
    time_ans.append(time)

def reset_ans():
    global cost_ans
    global time_ans
    cost_ans = []
    time_ans = []

class Sta(object):
    """station"""
    def __init__(self, station_name):
        super(Sta, self).__init__()
        self.station_name = station_name
        self.route = []

    def add_route(self, route):
        self.route.append(route)



class Route(object):
    """route"""
    def __init__(self, cost, time, next_station):
        super(Route, self).__init__()
        self.time = time
        self.cost = cost
        self.next_station = next_station

def search_route(now_station, gool_station, cost, time):
    """search route"""

    if now_station.station_name == gool_station.station_name:
        set_ans(cost, time)
        return

    elif len(now_station.route) == 0:
        return

    for r in now_station.route:
        search_route(
                r.next_station,
                gool_station,
                cost + r.cost,
                time + r.time)


def main():

    while True:
        reset_ans()
        n,m = map(int, raw_input().split())
        if n == 0 and m == 0:
            return

        stations = [Sta(x) for x in xrange(1,m+1) ]

        for i in xrange(n):
            a, b, cost, time = map(int, raw_input().split())
            tmp = Route(cost, time, stations[b-1])
            stations[a-1].add_route(tmp)

        k = input()
        for i in xrange(k):
            p, q, r = map(int, raw_input().split())
            search_route(stations[p-1], stations[q-1], 0, 0)
            if r == 0:
                print(min(cost_ans))
            else:
                print(min(time_ans))



if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
import math

def readnums():
    return map(int,raw_input().rstrip().split())

def makingpath(network,param='cost'):
    N = len(network)
    path = [[float("inf") for j in range(0,N)] for i in range(0,N)]
    for i in range(1,N):
        for j in range(i+1,N):
            if j in network[i]:
                path[i][j] = path[j][i] = network[i][j][param]
    for k in range(1,N):
        for i in range(1,N):
            for j in range(i+1,N):
                if path[i][j] > path[i][k] + path[k][j]:
                    path[i][j] = path[i][k] + path[k][j]
    return path

[n,m] = readnums()
stations = [{} for i in range(0,m+1)]
for i in range(0,n):
    [a,b,cost,time] = readnums()
    stations[a][b] = stations[b][a] = {'cost':float(cost), 'time':float(time) }
costnet = makingpath(stations,'cost')
timenet = makingpath(stations,'time')

[k] = readnums()
for i in range(0,k):
    [start,goal,inquiry] = readnums()
    if inquiry == 0:
        print int(costnet[start][goal])
    else:
        print int(timenet[start][goal])

Submission status: Runtime Error

Solution code:
import sys
import math

def readnums():
    return map(int,raw_input().split())

def makingpath(network,param='cost'):
    N = len(network)
    path = [[float("inf") for j in range(0,N)] for i in range(0,N)]
    for i in range(1,N):
        for j in range(i+1,N):
            if j in network[i]:
                path[i][j] = path[j][i] = network[i][j][param]
    for k in range(1,N):
        for i in range(1,N):
            for j in range(i+1,N):
                if path[i][j] > path[i][k] + path[k][j]:
                    path[i][j] = path[i][k] + path[k][j]
    return path

[n,m] = readnums()
stations = [{} for i in range(0,m+1)]
for i in range(0,n):
    [a,b,cost,time] = readnums()
    stations[a][b] = stations[b][a] = {'cost':float(cost), 'time':float(time) }
costnet = makingpath(stations,'cost')
timenet = makingpath(stations,'time')

[k] = readnums()
for i in range(0,k):
    [start,goal,inquiry] = readnums()
    if inquiry == 0:
        print int(costnet[start][goal])
    else:
        print int(timenet[start][goal])

Submission status: Runtime Error

Solution code:
def readnums():
    return map(int,raw_input().split())

def makingpath(network,param='cost'):
    N = len(network)
    path = [[float("inf") for j in range(0,N)] for i in range(0,N)]
    for i in range(1,N):
        for j in range(i+1,N):
            if j in network[i]:
                path[i][j] = path[j][i] = network[i][j][param]
    for k in range(1,N):
        for i in range(1,N):
            for j in range(i+1,N):
                if path[i][j] > path[i][k] + path[k][j]:
                    path[i][j] = path[i][k] + path[k][j]
    return path

[n,m] = readnums()
stations = [{} for i in range(0,m+1)]
for i in range(0,n):
    [a,b,cost,time] = readnums()
    stations[a][b] = stations[b][a] = {'cost':float(cost), 'time':float(time) }
costnet = makingpath(stations,'cost')
timenet = makingpath(stations,'time')

[k] = readnums()
for i in range(0,k):
    [start,goal,inquiry] = readnums()
    if inquiry == 0:
        print int(costnet[start][goal])
    else:
        print int(timenet[start][goal])
exit(0)