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: Time Limit Exceeded

Solution code:
""" Created by Jieyi on 7/28/16. """
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(graph, start, total_vertices):
    h = []
    shortest_path = [0 if i == start else sys.maxsize for i in range(total_vertices + 1)]
    heapq.heappush(h, (start, 0))

    while True:
        if 0 == len(h):
            break
        vertex, value = heapq.heappop(h)

        for k, v in graph.get(vertex):
            if shortest_path[k] > value + v:
                shortest_path[k] = value + v
                heapq.heappush(h, (k, shortest_path[k]))

    return shortest_path


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

        # Create two maps.
        g_money = defaultdict(list)
        g_time = defaultdict(list)

        # Set two maps.
        for _ in range(n):
            start, end, money, time = map(int, input().split())
            g_money[start].append((end, money))
            g_money[end].append((start, money))
            g_time[start].append((end, time))
            g_time[end].append((start, time))

        # 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)
            ans = dijkstra(m, start, s)
            print(ans[end])


def main():
    algorithm()


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
""" Created by Jieyi on 7/28/16. """
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(graph, start, end, total_vertices):
    h = []
    shortest_path = [0 if i == start else sys.maxsize for i in range(total_vertices + 1)]
    heapq.heappush(h, (start, 0))

    while True:
        vertex, value = heapq.heappop(h)
        if end == vertex:
            break

        for k, v in graph.get(vertex):
            if shortest_path[k] > value + v:
                shortest_path[k] = value + v
                heapq.heappush(h, (k, shortest_path[k]))

    return shortest_path


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

        # Create two maps.
        g_money = defaultdict(list)
        g_time = defaultdict(list)

        # Set two maps.
        for _ in range(n):
            start, end, money, time = map(int, input().split())
            g_money[start].append((end, money))
            g_money[end].append((start, money))
            g_time[start].append((end, time))
            g_time[end].append((start, time))

        # 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)
            ans = dijkstra(m, start, end, s)
            print(ans[end])


def main():
    algorithm()


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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


def dijkstra(graph, start, end, total_vertices):
    h = []
    shortest_path = [0 if i == start else sys.maxsize for i in range(total_vertices + 1)]
    heapq.heappush(h, (start, 0))

    while True:
        vertex, value = heapq.heappop(h)
        if end == vertex:
            break

        for k, v in graph.get(vertex):
            if shortest_path[k] > value + v:
                shortest_path[k] = value + v
                heapq.heappush(h, (k, shortest_path[k]))

    return shortest_path


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

        # Create two maps.
        g_money = defaultdict(list)
        g_time = defaultdict(list)

        # Set two maps.
        for _ in range(n):
            start, end, money, time = map(int, input().split())
            g_money[start].append((end, money))
            g_money[end].append((start, money))
            g_time[start].append((end, time))
            g_time[end].append((start, time))

        # 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)
            ans = dijkstra(m, start, end, s)
            print(ans[end])


def main():
    algorithm()


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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])

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: Time Limit Exceeded

Solution code:
while True:
    n, m = list(map(int,input().split()))
    if n == 0 and m == 0:
        break
    # ??°????????\???
    cost =  [[10000000 for i in range(m+1)] for j in range(m+1)]
    time =  [[10000000 for i in range(m+1)] for j in range(m+1)]
    for i in range(n):
        a, b, c, t = list(map(int, input().split()))
        cost[a][b] = cost[b][a] = c
        time[a][b] = time[b][a] = t

    # ???????????£???????????????
    for k in range(m+1):
        for i in range(m+1):
            for j in range(m+1):
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
                time[i][j] = min(time[i][j], time[i][k] + time[k][j])

    # ????????????
    k = int(input())
    p = []
    for i in range(k):
        p = list(map(int, input().split()))
        if p[2] == 0: print(cost[p[0]][p[1]])
        else: print(time[p[0]][p[1]])

Submission status: Time Limit Exceeded

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(V):
        for i in range(V):
            for j in range(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 _ 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: Time Limit Exceeded

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(1, 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 _ 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: Time Limit Exceeded

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(1, V):
                if dp[i][k][0] + dp[k][j][0] < dp[i][j][0]:
                    dp[i][j][0] = dp[i][k][0] + dp[k][j][0]
                if dp[i][k][1] + dp[k][j][1] < dp[i][j][1]:
                    dp[i][j][1] = dp[i][k][1] + dp[k][j][1]


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

        warshallFloyd(m+1, dp)

        k = int(input())
        for _ in range(k):
            p, q, r = map(int, input().split())
            if r == 0:          #  cost
                print(dp[p][q][1])
            else:               #  time
                print(dp[p][q][0])



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

Submission status: Time Limit Exceeded

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(1, 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:])

Submission status: Time Limit Exceeded

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(1, V):
                if dp[i][k] + dp[k][j] < dp[i][j]:
                    dp[i][j] = dp[i][k] + dp[k][j]


dp_time = []
dp_cost = []
def main(args):
    global dp_time
    global dp_cost
    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:])

Submission status: Time Limit Exceeded

Solution code:
import copy as c
CEIL = 2000000000

def exploreMin(now, goal, mode, history, ans, lines):
    #mode=0: MinCost;mode=1: MinTime
    #print(lines)
    if now == goal:
        #print('??\????????±??????')
        return ans
    if now in history: return CEIL
    minCostOrTime = CEIL
    for destination in lines[now]:
        exploreAns = exploreMin(destination[0], goal, mode, c.deepcopy(history)+[now],
                                ans+destination[mode+1], lines)
        #print(exploreAns)
        if minCostOrTime > exploreAns: minCostOrTime = exploreAns
    return minCostOrTime
'''
def findMin(start, goal, mode):
    minAnswer=100000
    if minAnswer > xplore(start, goal, mode, []):

    return minAnswer
'''
def dprint(a):
    print('debug:', end='')
    print(a)

def main():
    input1 = input().split(' ')
    #dprint(input1)
    if input1[0] == '0': return True
    lines=[[] for i in range(int(input1[1]))]
    for lineIndex in range(int(input1[0])):
        input2 = input().split(' ')
        #print('debug:', end='')
        #print(input2)
        lines[int(input2[0])-1].append([int(input2[1])-1, int(input2[2]), int(input2[3])])
        lines[int(input2[1])-1].append([int(input2[0])-1, int(input2[2]), int(input2[3])])
    #print(lines[0][0][1])
    setnum = int(input())
    #a = '\n'
    for out in range(setnum):
        #if out==setnum-1: a=''
        input3 = input().split(' ')
        #print([].append(1))
        print(exploreMin(int(input3[0])-1, int(input3[1])-1, int(input3[2]), [], 0, lines))

if __name__ == '__main__':
    while True:
        if main(): break

Submission status: Time Limit Exceeded

Solution code:
import copy as c
CEIL = 2000000000

def exploreMin(now, goal, mode, history, ans, lines):
    #mode=0: MinCost;mode=1: MinTime
    #print(lines)
    if now == goal:
        #print('??\????????±??????')
        return ans
    if now in history: return CEIL
    minCostOrTime = CEIL
    for destination in lines[now]:
        if minCostOrTime < destination[mode+1]: continue
        exploreAns = exploreMin(destination[0], goal, mode, c.deepcopy(history)+[now],
                                ans+destination[mode+1], lines)
        #print(exploreAns)
        if minCostOrTime > exploreAns: minCostOrTime = exploreAns
    return minCostOrTime
'''
def findMin(start, goal, mode):
    minAnswer=100000
    if minAnswer > xplore(start, goal, mode, []):

    return minAnswer
'''
def dprint(a):
    print('debug:', end='')
    print(a)

def main():
    input1 = input().split(' ')
    #dprint(input1)
    if input1[0] == '0': return True
    lines=[[] for i in range(int(input1[1]))]
    for lineIndex in range(int(input1[0])):
        input2 = input().split(' ')
        #print('debug:', end='')
        #print(input2)
        lines[int(input2[0])-1].append([int(input2[1])-1, int(input2[2]), int(input2[3])])
        lines[int(input2[1])-1].append([int(input2[0])-1, int(input2[2]), int(input2[3])])
    #print(lines[0][0][1])
    setnum = int(input())
    #a = '\n'
    for out in range(setnum):
        #if out==setnum-1: a=''
        input3 = input().split(' ')
        #print([].append(1))
        print(exploreMin(int(input3[0])-1, int(input3[1])-1, int(input3[2]), [], 0, lines))

if __name__ == '__main__':
    while True:
        if main(): break

Submission status: Time Limit Exceeded

Solution code:
import copy as c
CEIL = 2000000000

def exploreMin(now, goal, mode, history, ans, lines):
    #mode=0: MinCost;mode=1: MinTime
    #print(lines)
    if now == goal:
        #print('??\????????±??????')
        return ans
    if now in history: return CEIL
    minCostOrTime = CEIL
    for destination in lines[now]:
        if minCostOrTime < ans+destination[mode+1]: continue
        exploreAns = exploreMin(destination[0], goal, mode, c.deepcopy(history)+[now],
                                ans+destination[mode+1], lines)
        #print(exploreAns)
        if minCostOrTime > exploreAns: minCostOrTime = exploreAns
    return minCostOrTime
'''
def findMin(start, goal, mode):
    minAnswer=100000
    if minAnswer > xplore(start, goal, mode, []):

    return minAnswer
'''
def dprint(a):
    print('debug:', end='')
    print(a)

def main():
    input1 = input().split(' ')
    #dprint(input1)
    if input1[0] == '0': return True
    lines=[[] for i in range(int(input1[1]))]
    for lineIndex in range(int(input1[0])):
        input2 = input().split(' ')
        #print('debug:', end='')
        #print(input2)
        lines[int(input2[0])-1].append([int(input2[1])-1, int(input2[2]), int(input2[3])])
        lines[int(input2[1])-1].append([int(input2[0])-1, int(input2[2]), int(input2[3])])
    #print(lines[0][0][1])
    setnum = int(input())
    #a = '\n'
    for out in range(setnum):
        #if out==setnum-1: a=''
        input3 = input().split(' ')
        #print([].append(1))
        print(exploreMin(int(input3[0])-1, int(input3[1])-1, int(input3[2]), [], 0, lines))

if __name__ == '__main__':
    while True:
        if main(): break

Submission status: Time Limit Exceeded

Solution code:
import math


class WeightedEdge:
    """Weighted edge."""

    def __init__(self, a, b, weight):
        self.a = a
        self.b = b
        self.weight = weight

    def __repr__(self):
        return "(%d - %d: %d)" % (self.a, self.b, self.weight)

    def __lt__(self, other):
        return self.a < other.b


class EdgeWeightedGraph:
    """Undirected Edge-weighted graph (1-n indexed)."""

    def __init__(self, V):
        self.__adj = [[] for _ in range(V + 1)]

    def add_edge(self, a, b, weight):
        self.__adj[a].append(WeightedEdge(a, b, weight))
        self.__adj[b].append(WeightedEdge(b, a, weight))

    def adj(self, a):
        return self.__adj[a]

    def num_nodes(self):
        return len(self.__adj) - 1


class FloydWarshall:
    """u a.k.a. WarshallFloyd.

    Find shortest paths between each combination of vertices in a graph.
    ???3????????????a, b, c???????????§???a???b???c??¨????????????a???c??¨??????????????????????????°a???c????????¢?????´??°?????????
    ????????????for???????????±?????????????????????????????¨.
    O(V^3)
    """

    # graph has nodes [1, n]
    def __init__(self, graph):
        n = graph.num_nodes()
        nodes = range(1, n + 1)
        self.__mat = [[math.inf for _ in range(n + 1)] for _ in range(n + 1)]
        self.__init_mat(graph, nodes)
        self.__compute(nodes)

    def __init_mat(self, graph, nodes):
        for i in nodes:
            self.__mat[i][i] = 0

        for i in nodes:
            for edge in graph.adj(i):
                self.__mat[edge.a][edge.b] = edge.weight

    def __compute(self, nodes):
        for i in nodes:  # via
            for j in nodes:  # from
                for k in nodes:  # to
                    val = self.__mat[j][i] + self.__mat[i][k]
                    if self.__mat[j][k] > val:
                        self.__mat[j][k] = val

    def distance(self, a, b):
        return self.__mat[a][b]


if __name__ == '__main__':
    while True:
        n, m = map(int, input().split())
        if n == 0 and m == 0:
            break

        g_cost = EdgeWeightedGraph(m)
        g_time = EdgeWeightedGraph(m)
        for _ in range(n):
            a, b, cost, time = map(int, input().split())
            g_cost.add_edge(a, b, cost)
            g_time.add_edge(a, b, time)

        fw_cost = FloydWarshall(g_cost)
        fw_time = FloydWarshall(g_time)
        k = int(input())
        for _ in range(k):
            p, q, r = map(int, input().split())
            if r == 0:
                ans = fw_cost.distance(p, q)
            else:
                ans = fw_time.distance(p, q)
            print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush


class WeightedEdge:
    """Weighted edge."""

    def __init__(self, a, b, weight):
        self.a = a
        self.b = b
        self.weight = weight

    def __repr__(self):
        return "(%d - %d: %d)" % (self.a, self.b, self.weight)

    def __lt__(self, other):
        return self.a < other.b


class EdgeWeightedGraph:
    """Undirected Edge-weighted graph (1-n indexed)."""

    def __init__(self, V):
        self.__adj = [[] for _ in range(V + 1)]

    def add_edge(self, a, b, weight):
        self.__adj[a].append(WeightedEdge(a, b, weight))
        self.__adj[b].append(WeightedEdge(b, a, weight))

    def adj(self, a):
        return self.__adj[a]

    def num_nodes(self):
        return len(self.__adj) - 1


class Dijkstra:
    """Single root shortest path by Dijkstra."""

    def __init__(self, graph, s):
        self.dist_to = [float('inf') for _ in range(graph.num_nodes() + 1)]
        self.dist_to[s] = 0
        pq = []
        heappush(pq, (0, s))
        while pq:
            w, a = heappop(pq)
            if self.dist_to[a] < w:
                continue
            for edge in graph.adj(a):
                if self.dist_to[edge.b] > self.dist_to[edge.a] + edge.weight:
                    self.dist_to[edge.b] = self.dist_to[edge.a] + edge.weight
                    heappush(pq, (self.dist_to[edge.b], edge.b))


if __name__ == '__main__':
    while True:
        n, m = map(int, input().split())
        if n == 0 and m == 0:
            break

        g_cost = EdgeWeightedGraph(m)
        g_time = EdgeWeightedGraph(m)
        for _ in range(n):
            a, b, cost, time = map(int, input().split())
            g_cost.add_edge(a, b, cost)
            g_time.add_edge(a, b, time)

        k = int(input())
        for _ in range(k):
            p, q, r = map(int, input().split())
            if r == 0:
                fw_cost = Dijkstra(g_cost, p)
                ans = fw_cost.dist_to[q]
            else:
                fw_time = Dijkstra(g_time, p)
                ans = fw_time.dist_to[q]
            print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop as hpop
from heapq import heappush as hpush

while True:
  n, m = map(int, input().split())
  
  if not n:
    break
  
  cost_edges = [[] for _ in range(m)]
  time_edges = [[] for _ in range(m)]

  for _ in range(n):
    a, b, c, t = map(int, input().split())
    cost_edges[a - 1].append((c, b - 1))
    cost_edges[b - 1].append((c, a - 1))
    time_edges[a - 1].append((t, b - 1))
    time_edges[b - 1].append((t, a - 1))
  
  k = int(input())

  for _ in range(k):
    start, goal, r = map(int ,input().split())
    start -= 1
    goal -= 1
    
    if r:
      edges = time_edges
    else:
      edges = cost_edges

    que = [(0, start)]
    visited = [False for _ in range(m)]
    
    while que:
      score, station = hpop(que)
      visited[station] = True
      
      if station == goal:
        print(score)
        break

      for c, to_station in edges[station]:
        if not visited[to_station]:
          hpush(que, (score + c, to_station))

Submission status: Time Limit Exceeded

Solution code:
# AOJ 0200 Traveling Alone: One-way Ticket of Youth
# Python3 2018.6.24 bal4u
# ワーシャルフロイド法

INF = 0x7fffffff

while 1:
	n, m = map(int, input().split())
	if n == 0: break
	tim = [[INF for j in range(m)] for i in range(m)]
	fee = [[INF for j in range(m)] for i in range(m)]
	for i in range(m): tim[i][i] = fee[i][i] = 0;
	for i in range(n):
		a, b, c, t = map(int, input().split())
		a -= 1
		b -= 1
		if fee[a][b] > c: fee[a][b] = fee[b][a] = c
		if tim[a][b] > t: tim[a][b] = tim[b][a] = t
	for k in range(m):
		for i in range(m):
			for j in range(m):
				if fee[i][k]+fee[k][j] < fee[i][j]: fee[i][j] = fee[i][k]+fee[k][j]
				if tim[i][k]+tim[k][j] < tim[i][j]: tim[i][j] = tim[i][k]+tim[k][j]
	k = int(input())
	for i in range(k):
		p, q, r = map(int, input().split())
		if (r): print(tim[p-1][q-1])
		else:   print(fee[p-1][q-1])

Submission status: Time Limit Exceeded

Solution code:
# AOJ 0200 Traveling Alone: One-way Ticket of Youth
# Python3 2018.6.24 bal4u
# ワーシャルフロイド法

INF = 0x7fffffff

while 1:
	n, m = map(int, input().split())
	if n == 0: break
	tim = [[INF for j in range(m)] for i in range(m)]
	fee = [[INF for j in range(m)] for i in range(m)]
	for i in range(m): tim[i][i] = fee[i][i] = 0;
	for i in range(n):
		a, b, c, t = map(int, input().split())
		a -= 1
		b -= 1
		if fee[a][b] > c: fee[a][b] = fee[b][a] = c
		if tim[a][b] > t: tim[a][b] = tim[b][a] = t
	for k in range(m):
		for i in range(m):
			if fee[i][k] == INF: continue
			for j in range(m):
				if fee[k][j] == INF: continue
				if fee[i][k]+fee[k][j] < fee[i][j]: fee[i][j] = fee[i][k]+fee[k][j]
				if tim[i][k]+tim[k][j] < tim[i][j]: tim[i][j] = tim[i][k]+tim[k][j]
	k = int(input())
	for i in range(k):
		p, q, r = map(int, input().split())
		if (r): print(tim[p-1][q-1])
		else:   print(fee[p-1][q-1])

Submission status: Time Limit Exceeded

Solution code:
import copy

class Staion:

    def __init__(self, id):
        self.id = id
        self.childs = []
        self.value = 10000000
        self.done = False

    def __lt__(self, other):
        return self.value < other.value

while True:

    n, m = [int(n) for n in raw_input().split()]
    if n == 0 and m == 0:
        break

    # input stations
    stations = []
    for i in xrange(m):
        stations.append(Staion(i + 1))
    for i in xrange(n):
        a, b, cost, time = [int(n) for n in raw_input().split()]
        stations[a - 1].childs.append((b, cost, time))
        stations[b - 1].childs.append((a, cost, time))

    # input query
    k = int(raw_input())
    for i in xrange(k):
        start, end, r = [int(n) for n in raw_input().split()]
        temp = copy.deepcopy(stations)
        temp[start - 1].value = 0
        queue = [temp[start - 1]]
        while queue:
            queue.sort()
            node = queue.pop(0)
            if node.id == end:
                print node.value
                break
            node.done = True
            for info in node.childs:
                child = temp[info[0] - 1]
                value = info[r + 1] + node.value
                if value < child.value:
                    child.value = value
                    if not child in queue:
                        queue.append(child)

Submission status: Time Limit Exceeded

Solution code:
import copy

class Staion:

    def __init__(self, id):
        self.id = id
        self.childs = []
        self.value = 10000000
        self.done = False

    def __lt__(self, other):
        return self.value < other.value

while True:
    n, m, k = 0, 0, 0
    n, m = [int(n) for n in raw_input().split()]
    if n == 0 and m == 0:
        break

    # input stations
    stations = []
    for i in xrange(m):
        stations.append(Staion(i + 1))
    for i in xrange(n):
        a, b, cost, time = [int(n) for n in raw_input().split()]
        stations[a - 1].childs.append((b, cost, time))
        stations[b - 1].childs.append((a, cost, time))

    # input query
    k = int(raw_input())
    for i in xrange(k):
        start, end, r = [int(n) for n in raw_input().split()]
        temp = copy.deepcopy(stations)
        temp[start - 1].value = 0
        queue = [temp[start - 1]]
        while queue:
            queue.sort()
            node = queue.pop(0)
            if node.id == end:
                print node.value
                break
            node.done = True
            for info in node.childs:
                child = temp[info[0] - 1]
                value = info[r + 1] + node.value
                if value < child.value:
                    child.value = value
                    if not child in queue:
                        queue.append(child)