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: Wrong Answer

Solution code:
import sys

inf = sys.maxsize

# 入力:graphと始点s
# 出力:始点sから各頂点tへの距離dist
def shortestPath(graph, s):
    n = len(graph)

    dist    = [inf for _ in range(n)]
    visited = [False for _ in range(n)]
    dist[s] = 0

    while True:
        idx, u  = -1, inf
        for i in range(n):
            if not visited[i] and dist[i] < u:
                idx = i
                u = dist[i]
        
        if u == inf: break
        
        visited[idx] = True

        for (next, w) in graph[idx]:
            newdist = w + dist[idx]
            if newdist < dist[next]:
                dist[next] = newdist
    return dist

def main():
    n, m = map(int, input().split())
    # 隣接リスト
    c_graph = [[] for _ in range(m)]
    t_graph = [[] for _ in range(m)]
    
    for i in range(n):
        a, b, cost, time = map(int, input().split())
        a -= 1
        b -= 1
        c_graph[a].append((b, cost))
        c_graph[b].append((a, cost))
        t_graph[a].append((b, time))
        t_graph[b].append((a, time))

    c_dist = [shortestPath(c_graph, s) for s in range(m)]
    t_dist = [shortestPath(t_graph, s) for s in range(m)]
    
    k = int(input())
    for i in range(k):
        p, q, r = map(int, input().split())
        p -= 1
        q -= 1
        if r == 0:
            print(c_dist[p][q])
        else:
            print(t_dist[p][q])

main()

Submission status: Wrong Answer

Solution code:
import sys
import heapq as h

inf = sys.maxsize

# おまじない
class heapq:
    def __init__(self):
        self.q = []

    def push(self,v):
        h.heappush(self.q, v)
    
    def pop(self):
        return h.heappop(self.q)

    def is_empty(self):
        return len(self.q) == 0

# 入力:graphと始点s
# 出力:始点sから各頂点tへの距離dist
def shortestPath0(graph, s):
    n = len(graph)

    dist    = [inf for _ in range(n)]
    visited = [False for _ in range(n)]
    dist[s] = 0

    while True:
        idx, u  = -1, inf
        for i in range(n):
            if not visited[i] and dist[i] < u:
                idx = i
                u = dist[i]
        
        if u == inf: break
        
        visited[idx] = True

        for (next, w) in graph[idx]:
            newdist = w + dist[idx]
            if newdist < dist[next]:
                dist[next] = newdist
    return dist

def shortestPath1(graph, s):
    n = len(graph)

    dist    = [inf for _ in range(n)]
    visited = [False for _ in range(n)]
    
    q = heapq()
    q.push((0, s))

    while not q.is_empty():
        (cur_dist, v) = q.pop()

        if visited[v] or dist[v] <= cur_dist:
            continue

        dist[v] = cur_dist
        visited[v] = True

        for next, w in graph[v]:
            if not visited[next] and dist[v] + w < dist[next]:
                q.push((dist[v] + w, next))

    return dist

def main():
    n, m = map(int, input().split())
    
    # 隣接リスト
    tgraph = [[] for _ in range(m)]
    cgraph = [[] for _ in range(m)]
    
    for i in range(n):
        a, b, cost, time = map(int, input().split())
        a -= 1
        b -= 1
        cgraph[a].append((b, cost))
        cgraph[b].append((b, cost))
        tgraph[a].append((b, time))
        tgraph[b].append((b, time))

    c_dist = [shortestPath1(cgraph, s) for s in range(m)]
    t_dist = [shortestPath1(tgraph, s) for s in range(m)]

    k = int(input())
    for i in range(k):
        p, q, r = map(int, input().split())
        p-=1
        q-=1
        if r == 0:
            print(c_dist[p][q])
        else:
            print(t_dist[p][q])
main()

Submission status: Wrong Answer

Solution code:
import sys
import heapq as h

inf = sys.maxsize

# おまじない
class heapq:
    def __init__(self):
        self.q = []

    def push(self,v):
        h.heappush(self.q, v)
    
    def pop(self):
        return h.heappop(self.q)

    def is_empty(self):
        return len(self.q) == 0

# 入力:graphと始点s
# 出力:始点sから各頂点tへの距離dist
def shortestPath0(graph, s):
    n = len(graph)

    dist    = [inf for _ in range(n)]
    visited = [False for _ in range(n)]
    dist[s] = 0

    while True:
        idx, u  = -1, inf
        for i in range(n):
            if not visited[i] and dist[i] < u:
                idx = i
                u = dist[i]
        
        if u == inf: break
        
        visited[idx] = True

        for (next, w) in graph[idx]:
            newdist = w + dist[idx]
            if newdist < dist[next]:
                dist[next] = newdist
    return dist

def shortestPath1(graph, s):
    n = len(graph)

    dist    = [inf for _ in range(n)]
    visited = [False for _ in range(n)]
    
    q = heapq()
    q.push((0, s))

    while not q.is_empty():
        (cur_dist, v) = q.pop()

        if visited[v] or dist[v] <= cur_dist:
            continue

        dist[v] = cur_dist
        visited[v] = True

        for next, w in graph[v]:
            if not visited[next] and dist[v] + w < dist[next]:
                q.push((dist[v] + w, next))

    return dist

def main():
    while True:
        n, m = map(int, input().split())
        if n == 0 and m == 0:
            break
        # 隣接リスト
        tgraph = [[] for _ in range(m)]
        cgraph = [[] for _ in range(m)]
        
        for i in range(n):
            a, b, cost, time = map(int, input().split())
            a -= 1
            b -= 1
            cgraph[a].append((b, cost))
            cgraph[b].append((b, cost))
            tgraph[a].append((b, time))
            tgraph[b].append((b, time))
            
        c_dist = [shortestPath0(cgraph, s) for s in range(m)]
        t_dist = [shortestPath0(tgraph, s) for s in range(m)]

        k = int(input())
        for i in range(k):
            p, q, r = map(int, input().split())
            p-=1
            q-=1
            if r == 0:
                print(c_dist[p][q])
            else:
                print(t_dist[p][q])
main()

Submission status: Wrong Answer

Solution code:
import sys
import heapq as h

inf = sys.maxsize

# おまじない
class heapq:
    def __init__(self):
        self.q = []

    def push(self,v):
        h.heappush(self.q, v)
    
    def pop(self):
        return h.heappop(self.q)

    def is_empty(self):
        return len(self.q) == 0

# 入力:graphと始点s
# 出力:始点sから各頂点tへの距離dist
def shortestPath0(graph, s):
    n = len(graph)

    dist    = [inf for _ in range(n)]
    visited = [False for _ in range(n)]
    dist[s] = 0

    while True:
        idx, u  = -1, inf
        for i in range(n):
            if not visited[i] and dist[i] < u:
                idx = i
                u = dist[i]
        
        if u == inf: break
        
        visited[idx] = True

        for (next, w) in graph[idx]:
            newdist = w + dist[idx]
            if newdist < dist[next]:
                dist[next] = newdist
    return dist

def shortestPath1(graph, s):
    n = len(graph)

    dist    = [inf for _ in range(n)]
    visited = [False for _ in range(n)]
    
    q = heapq()
    q.push((0, s))

    while not q.is_empty():
        (cur_dist, v) = q.pop()

        if visited[v] or dist[v] <= cur_dist:
            continue

        dist[v] = cur_dist
        visited[v] = True

        for next, w in graph[v]:
            if not visited[next] and dist[v] + w < dist[next]:
                q.push((dist[v] + w, next))

    return dist

def main():
    while True:
        n, m = map(int, input().split())
        if n == 0 and m == 0:
            break
        # 隣接リスト
        tgraph = [[] for _ in range(m)]
        cgraph = [[] for _ in range(m)]
        
        for i in range(n):
            a, b, cost, time = map(int, input().split())
            a -= 1
            b -= 1
            cgraph[a].append((b, cost))
            cgraph[b].append((b, cost))
            tgraph[a].append((b, time))
            tgraph[b].append((b, time))
            
        c_dist = [shortestPath1(cgraph, s) for s in range(m)]
        t_dist = [shortestPath1(tgraph, s) for s in range(m)]

        k = int(input())
        for i in range(k):
            p, q, r = map(int, input().split())
            p-=1
            q-=1
            if r == 0:
                print(c_dist[p][q])
            else:
                print(t_dist[p][q])
main()

Submission status: Wrong Answer

Solution code:
inf = 0x10101010

def solve(A, strt):
	cost = [inf]*m  
	visited = [False]*m
	cost[strt] = 0
	
	while 1:
		min = inf 
		next = -1   
		visited[strt] = True 
		for i in range(m):
			if visited[i]:
				continue
			if A[strt][i]:
				d = cost[strt] + A[strt][i]
				if d < cost[i]:
					cost[i] = d
				if cost[i] < min:
					min = cost[i]
					next = i
		strt = next 
		if next == -1: break
	return cost
						



while 1:
	n, m = map(int, raw_input().split())
	if n == 0:
		break
	T = [[0]*m for i in range(m)]
	C = [[0]*m for i in range(m)]

	for i in range(n):
		a, b, c, t = map(int, raw_input().split()) 
		T[a-1][b-1] = T[b-1][a-1] = t 
		C[a-1][b-1] = C[b-1][a-1] = c
	TS = [solve(T, i) for i in range(m)]
	CS = [solve(C, i) for i in range(m)]
	for i in range(input()):
		a, b, q = map(int, raw_input().split())
		if q == 0:
			print CS[a-1][b-1]
		else:
			print TS[a-1][b-1]

Submission status: Wrong Answer

Solution code:
import sys
from copy import deepcopy


def dijkstra(path_map, start=0):
    arr_shortest_path = path_map[start]
    stack = []

    # Until all vertices put into stack.
    while 1:
        if len(stack) is len(arr_shortest_path):
            break

        # Pick the smallest value from the arr_shortest_path is not including vertices in the stack.
        tmp_arr = arr_shortest_path[:]
        for i in range(len(stack)):
            tmp_arr[stack[i]] = sys.maxsize
        mini_vertex = arr_shortest_path.index(min(tmp_arr))
        stack.append(mini_vertex)

        # Calculate the smallest value's vertex with all vertices which it could go.
        for i in range(len(arr_shortest_path)):
            if arr_shortest_path[i] > arr_shortest_path[mini_vertex] + path_map[mini_vertex][i]:
                arr_shortest_path[i] = arr_shortest_path[mini_vertex] + path_map[mini_vertex][i]

    return arr_shortest_path


def algorithm():
    n, s = map(int, input().split(' '))
    g_money = [[sys.maxsize for _ in range(s)] for _ in range(s)]
    for c in range(s):
        g_money[c][c] = 0
    g_time = deepcopy(g_money)

    for _ in range(n):
        x, y, money, time = map(int, input().split(' '))
        x -= 1
        y -= 1
        g_money[x][y] = money
        g_time[x][y] = time

    for n in range(int(input())):
        inp = list(map(int, input().split(' ')))
        if len(inp) == 2:
            break
        else:
            start, end, category = inp
        m = {0: g_money, 1: g_time}.get(category)
        ans = dijkstra(m, start - 1)
        print(ans[end - 1])


def main():
    algorithm()


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
adj = []
def search(goal, path, flag, s, result):
    c = path[-1]
    if goal - 1 == c:
        if s < result: result = s
    else:
        for i in adj[c]:
            if i[0] not in path:
                path.append(i[0])
                s += i[1] if flag == 0 else i[2]
                result = search(goal, path, flag, s, result)
                path.pop()
                s -= i[1] if flag == 0 else i[2]
    return result

n, m = map(int, raw_input().split())
adj = [[] for i in range(n)]
for i in range(n):
    x, y, c, t = map(int, raw_input().split())
    adj[x - 1].append([y - 1, c, t])
    adj[y - 1].append([x - 1, c, t])
n = input()
for i in range(n):
    start, goal, flag = map(int, raw_input().split())
    print search(goal, [start - 1], flag, 0, 9999)

Submission status: Wrong Answer

Solution code:
""" Created by Jieyi on 7/28/16. """
import copy
import io
import sys
from collections import defaultdict
import heapq

if len(sys.argv) > 1:
    filename = sys.argv[1]
    inp = ''.join(open(filename, "r").readlines())
    sys.stdin = io.StringIO(inp)


def dijkstra(p, q, E):
    h = []
    d = defaultdict(lambda: 100000000)
    heapq.heappush(h, (0, p))

    while h:
        c, i = heapq.heappop(h)
        if i == q:
            return c
        for j in E[i]:
            nc = c + E[i][j]
            if d[j] > nc:
                d[j] = nc
                heapq.heappush(h, (nc, j))


def algorithm():
    while True:
        n, s = map(int, input().split())
        if n == 0 and s == 0:
            break

        # Create two maps.
        # g_money = [[sys.maxsize for _ in range(s)] for _ in range(s)]
        # g_time = copy.deepcopy(g_money)
        g_money = defaultdict(defaultdict)
        g_time = defaultdict(defaultdict)

        # Set two maps.
        for _ in range(n):
            x, y, m, t = map(int, input().split())
            g_money[x - 1][y - 1] = m
            g_time[x - 1][y - 1] = t

        # Calculate the shortest path.
        for n in range(int(input())):
            start, end, category = list(map(int, input().split()))
            m = {0: g_money, 1: g_time}.get(category)

            print(dijkstra(start - 1, end - 1, m))


def main():
    algorithm()


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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):
    pass
#   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: Wrong Answer

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 = [999]
    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: Wrong Answer

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 = [999]
    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: Wrong Answer

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 = [99999]
    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: Wrong Answer

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 = [9999999999]
    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: Wrong Answer

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

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, jikan):
        self.now_station = now_station
        self.next_station = next_station
        self.price = price
        self.jikan = jikan

def search_path(stations, come_from, go_to, search_type):
    result = [9999999999]
    q = []
    for distination in stations[come_from].routes:
        new_path = Path(come_from, distination.station_number, distination.price, distination.jikan)
        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.jikan
            result.append(r)
        for distination in stations[path.next_station].routes:
            update_price = path.price + distination.price
            update_jikan = path.jikan + distination.jikan
            next_path = Path(path.next_station, distination.station_number, update_price, update_jikan)
            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, jikan = map(int, input().split(" "))
    route = Route(go_to - 1, price, jikan)
    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: Wrong Answer

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 = [9999999999]
    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: Wrong Answer

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_path = [now_station]
        self.use_price = use_price
        self.use_time = use_time
    def already_path(self,station):
        return station in self.use_path
 
def search(stations, start, end, search_type):
    result = [9999999999]
    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:
            if status.already_path(route.next_station):
                continue
            status.use_price = route.need_price + status.use_price
            status.use_time = route.need_time + status.use_time
            status.now_station = route.next_station
            status.use_path.append(route.next_station)
            queue.append(status)
    print(sorted(result)[0])
 
while True:
    read_line = input()
    if read_line == "0 0":
        break
    route_count, station_count = map(int, read_line.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: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0200

"""
import sys
from sys import stdin
input = stdin.readline


def warshallFloyd(V, dp):
    for k in range(1, V):
        for i in range(1, V):
            for j in range(i, V):
                if dp[i][k] + dp[k][j] < dp[i][j]:
                    dp[i][j] = dp[i][k] + dp[k][j]


def main(args):
    while True:
        n, m = map(int, input().split())
        if n == 0 and m == 0:
            break
        dp_time = [[9999999] * (m+1) for _ in range(m+1)]
        dp_cost = [[9999999] * (m+1) for _ in range(m+1)]
        for i in range(m+1):
            dp_time[i][i] = 0
            dp_cost[i][i] = 0

        for _ in range(n):
            a, b, cost, time = map(int, input().split())
            dp_time[a][b] = time
            dp_time[b][a] = time
            dp_cost[a][b] = cost
            dp_cost[b][a] = cost

        warshallFloyd(m+1, dp_time)
        warshallFloyd(m+1, dp_cost)

        k = int(input())
        for _ in range(k):
            p, q, r = map(int, input().split())
            if r == 0:
                print(dp_cost[p][q])
            else:
                print(dp_time[p][q])



if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0200

"""
import sys
from sys import stdin
input = stdin.readline


def warshallFloyd(V, dp):
    for k in range(1, V):
        for i in range(1, V):
            for j in range(i, V):
                if dp[i][k] + dp[k][j] < dp[i][j]:
                    dp[i][j] = dp[i][k] + dp[k][j]


def main(args):
    while True:
        n, m = map(int, input().split())
        if n == 0 and m == 0:
            break
        dp_time = [[float('inf')] * (m+1) for _ in range(m+1)]
        dp_cost = [[float('inf')] * (m+1) for _ in range(m+1)]
        for i in range(m+1):
            dp_time[i][i] = 0
            dp_cost[i][i] = 0

        for _ in range(n):
            a, b, cost, time = map(int, input().split())
            dp_time[a][b] = time
            dp_time[b][a] = time
            dp_cost[a][b] = cost
            dp_cost[b][a] = cost

        warshallFloyd(m+1, dp_time)
        warshallFloyd(m+1, dp_cost)

        k = int(input())
        for _ in range(k):
            p, q, r = map(int, input().split())
            if r == 0:
                print(dp_cost[p][q])
            else:
                print(dp_time[p][q])



if __name__ == '__main__':
    main(sys.argv[1:])