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:
import heapq
def dijkstra(graph, size, start, r):
    distance = [float('inf')] * size
    distance[start] = 0
    que = []
    heapq.heappush(que, (0, start))
    while len(que):
        _, u = heapq.heappop(que)
        for length, vi in graph[u]:
            if distance[vi] > distance[u] + length[r]:
                distance[vi] = distance[u] + length[r]
                heapq.heappush(que, (distance[vi], vi))
    return distance

import sys
f = sys.stdin

import collections

while True:
    n, m = map(int, f.readline().split())
    if n == 0:
        break
    abct = [list(map(int, f.readline().split())) for _ in range(n)]
    graph = collections.defaultdict(list)
    for ai, bi, cost, time in abct:
        graph[ai].append(((cost, time), bi))
        graph[bi].append(((cost, time), ai))
        
    k = int(f.readline())
    
    dist = {}
    for i in range(k):
        p, q, r = map(int, f.readline().split())
        
        if (q,r) in dist:
            p, q = q, p
        elif (p,r) not in dist:
            dist[(p,r)] = dijkstra(graph, m + 1, p, r)
        print(dist[(p,r)][q])

Submission status: Time Limit Exceeded

Solution code:
import sys
f = sys.stdin

while True:
    n, m = map(int, f.readline().split())
    if n == 0:
        break
    abct = [list(map(int, f.readline().split())) for _ in range(n)]
    dist = [[(float('inf'),float('inf'))  for j in range(m)] for i in range(m)]    
    for ai, bi, cost, time in abct:
        dist[ai - 1][bi - 1] = (cost, time)
    for k in range(m):
        for i in range(m):
            for j in range(m):
                if dist[i][j][0] > dist[i][k][0] + dist[k][j][0]:
                    dist[i][j] = (dist[i][k][0] + dist[k][j][0], dist[i][j][1])
                if dist[i][j][1] > dist[i][k][1] + dist[k][j][1]:
                    dist[i][j] = (dist[i][j][0], dist[i][k][1] + dist[k][j][1])
        
    k = int(f.readline())
    for i in range(k):
        p, q, r = map(int, f.readline().split())
        print(dist[p - 1][q - 1][r])

Submission status: Time Limit Exceeded

Solution code:
def warshall_floyd(d):
    for k in range(len(d)):
        for i in range(len(d)):
            for j in range(len(d)):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]

import sys
f = sys.stdin

while True:
    n, m = map(int, f.readline().split())
    if n == 0:
        break
    abct = [list(map(int, f.readline().split())) for _ in range(n)]
    
    d = [[[float('inf')] * m for i in range(m)], [[float('inf')] * m for i in range(m)]]
    
    for ai, bi, ci, ti in abct:
        d[0][ai - 1][bi - 1] = ci
        d[1][ai - 1][bi - 1] = ti

    warshall_floyd(d[0])
    warshall_floyd(d[1])
        
    for i in range(int(f.readline())):
        p, q, r = map(int, f.readline().split())
        print(d[r][p - 1][q - 1])

Submission status: Time Limit Exceeded

Solution code:
def warshall_floyd(d):
    for k in range(len(d)):
        for i in range(len(d)):
            for j in range(len(d)):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]

import sys
f = sys.stdin

while True:
    n, m = map(int, f.readline().split())
    if n == 0:
        break
    abct = [list(map(int, f.readline().split())) for _ in range(n)]
    
    d = [[[float('inf')] * m for i in range(m)], [[float('inf')] * m for i in range(m)]]
    
    for ai, bi, ci, ti in abct:
        d[0][ai - 1][bi - 1] = d[0][bi - 1][ai - 1] = ci
        d[1][ai - 1][bi - 1] = d[1][bi - 1][ai - 1] = ti

    warshall_floyd(d[0])
    warshall_floyd(d[1])
        
    for i in range(int(f.readline())):
        p, q, r = map(int, f.readline().split())
        print(d[r][p - 1][q - 1])

Submission status: Time Limit Exceeded

Solution code:
import heapq
def dijkstra(graph, size, start):
    distance = [float('inf')] * size
    distance[start] = 0
    que = []
    heapq.heappush(que, (0, start))
    while len(que):
        _, u = heapq.heappop(que)
        for length, vi in graph[u]:
            if distance[vi] > distance[u] + length:
                distance[vi] = distance[u] + length
                heapq.heappush(que, (distance[vi], vi))
    return distance

import sys
f = sys.stdin

import collections

while True:
    n, m = map(int, f.readline().split())
    if n == 0:
        break
    abct = [list(map(int, f.readline().split())) for _ in range(n)]
    d = [collections.defaultdict(list), collections.defaultdict(list)]
    
    for ai, bi, cost, time in abct:
        d[0][ai].append((cost, bi))
        d[0][bi].append((cost, ai))
        d[1][ai].append((time, bi))
        d[1][bi].append((time, ai))
        
    k = int(f.readline())
    
    dist = {}
    for i in range(k):
        p, q, r = map(int, f.readline().split())
        
        if (q,r) in dist:
            p, q = q, p
        elif (p,r) not in dist:
            dist[(p,r)] = dijkstra(d[r], m + 1, p)
        print(dist[(p,r)][q])

Submission status: Time Limit Exceeded

Solution code:
while(1):
    [n,m]=[int(x) for x in raw_input().split()]
    if n==0:
        break
    else:
        C=[[9999 for x in range(m+1)] for y in range (m+1)]
        T=[[9999 for x in range(m+1)] for y in range (m+1)]
        for i in range(n):
            [a,b,c,t]=[int(x) for x in raw_input().split()]
            C[a][b]=c
            C[b][a]=c
            T[a][b]=t
            T[b][a]=t
        for i in range(1,m+1):
            C[i][i]=0
            T[i][i]=0
        for k in range(1,m+1):
            for i in range(1,m+1):
                for j in range(1,m+1):
                    if C[i][j]>C[i][k]+C[k][j]:
                        C[i][j]=C[i][k]+C[k][j]
                    if T[i][j]>T[i][k]+T[k][j]:
                        T[i][j]=T[i][k]+T[k][j]
        Q=int(raw_input())
        for i in range(Q):
            [p,q,r]=[int(x) for x in raw_input().split()]
            if r:
                print T[p][q]
            else:
                print C[p][q]

Submission status: Time Limit Exceeded

Solution code:
def search(goal, path, t_cost, t_time, m_cost, m_time):
    n = path[len(path) - 1]
    if n == goal:
        if m_cost > t_cost: m_cost = t_cost
        if m_time > t_time: m_time = t_time
    else:
        for x in adj[n]:
            if x[0] not in path:
                path.append(x[0])
                t_cost += x[1]
                t_time += x[2]
                m_cost, m_time = search(goal, path, t_cost, t_time, m_cost, m_time)
                path.pop()
                t_cost -= x[1]
                t_time -= x[2]
    return m_cost, m_time

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

    adj = [[] for i in range(m)]
    for i in range(n):
        a, b, cost, time = map(int, raw_input().split())
        adj[a - 1].append([b - 1, cost, time])
        adj[b - 1].append([a - 1, cost, time])

    k = input()
    for i in range(k):
        p, q, r = map(int, raw_input().split())
        cost, time = search(q - 1, [p - 1], 0, 0, 1000, 1000)
        if r == 0: print cost
        else: print time

Submission status: Time Limit Exceeded

Solution code:
inf = 100000

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

    s_min = [[[inf] * 2 for _ in range(m)] for _ in range(m)]
    for i in range(n):
        a, b, cost, time = [int(x) for x in raw_input().split()]
        s_min[a - 1][b - 1][0] = s_min[b - 1][a - 1][0] = cost
        s_min[a - 1][b - 1][1] = s_min[b - 1][a - 1][1] = time

    for i in range(m):
        for j in range((i + 1), m):
            for k in range(m):
                s_min[i][j][0] = s_min[j][i][0] = min(s_min[k][i][0] + s_min[k][j][0], s_min[i][j][0])
                s_min[i][j][1] = s_min[j][i][1] = min(s_min[k][i][1] + s_min[k][j][1], s_min[i][j][1])

    k = input()
    for i in range(k):
        p, q, r = [int(x) for x in raw_input().split()]
        print s_min[p -1][q - 1][r]

Submission status: Time Limit Exceeded

Solution code:
inf = 100000

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

    s_min = [[[inf] * 2 for _ in range(m)] for _ in range(m)]
    for i in range(n):
        a, b, cost, time = [int(x) for x in raw_input().split()]
        s_min[a - 1][b - 1][0] = s_min[b - 1][a - 1][0] = cost
        s_min[a - 1][b - 1][1] = s_min[b - 1][a - 1][1] = time

    for i in range(m):
        for j in range(m):
            for k in range(m):
                s_min[i][j][0] = s_min[j][i][0] = min(s_min[k][i][0] + s_min[k][j][0], s_min[i][j][0])
                s_min[i][j][1] = s_min[j][i][1] = min(s_min[k][i][1] + s_min[k][j][1], s_min[i][j][1])

    k = input()
    for i in range(k):
        p, q, r = [int(x) for x in raw_input().split()]
        print s_min[p -1][q - 1][r]

Submission status: Time Limit Exceeded

Solution code:
inf = 100000

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

    s_min = [[[inf] * 2 for _ in range(m)] for _ in range(m)]
    for i in range(n):
        a, b, cost, time = [int(x) for x in raw_input().split()]
        s_min[a - 1][b - 1][0] = s_min[b - 1][a - 1][0] = cost
        s_min[a - 1][b - 1][1] = s_min[b - 1][a - 1][1] = time

    for k in range(m):
        for i in range(m):
            for j in range(m):
                s_min[i][j][0] = s_min[j][i][0] = min(s_min[k][i][0] + s_min[k][j][0], s_min[i][j][0])
                s_min[i][j][1] = s_min[j][i][1] = min(s_min[k][i][1] + s_min[k][j][1], s_min[i][j][1])

    k = input()
    for i in range(k):
        p, q, r = [int(x) for x in raw_input().split()]
        print s_min[p -1][q - 1][r]

Submission status: Time Limit Exceeded

Solution code:
def f(p, q, x, total, route):
    global short
    total += x
    route.append(p)
    if short is not None and short <= total:
        return
    elif p == q:
        short = total
        return True
    else:
        for a, b in data:
            cost, time = data[(a, b)]
            if a == p and not b in route:
                if f(b, q, cost if r == 0 else time, total, route[:]):
                    return
            elif b == p and not a in route:
                if f(a, q, cost if r == 0 else time, total, route[:]):
                    return

while True:
    n, m = map(int, raw_input().split())
    if n == m == 0: break
    data = {}
    for i in range(n):
        a, b, c, t = map(int, raw_input().split())
        data[(a, b)] = [c, t]
    for i in range(int(raw_input())):
        s, g, r = map(int, raw_input().split())
        short = None
        f(s, g, 0, 0, [])
        print short

Submission status: Time Limit Exceeded

Solution code:
def f(s, cost, res):
    if s == g:
        return cost[g]
    res.append(s)
    for k, v in data.items():
        a, b = k
        c = v[0] if r == 0 else v[1]
        if s == a:
            if not b in res:
                if not b in cost or cost[s]+c < cost[b]:
                    cost[b] = cost[s]+c
        elif s == b:
            if not a in res:
                if not a in cost or cost[s]+c < cost[a]:
                    cost[a] = cost[s]+c
    del cost[s]
    x = sorted(cost.items(), key=lambda x: x[1])[0][0]
    return f(x, cost, res)

while True:
    n, m = map(int, raw_input().split())
    if n == m == 0: break
    data = {}
    for i in range(n):
        a, b, c, t = map(int, raw_input().split())
        data[(a, b)] = [c, t]
    for i in range(int(raw_input())):
        s, g, r = map(int, raw_input().split())
        print f(s, {s:0}, [])

Submission status: Time Limit Exceeded

Solution code:
def f(s, cost, res):
    if s == g:
        return cost[g]
    res.append(s)
    for k, v in data.items():
        a, b = k
        c = v[0] if r == 0 else v[1]
        if s == a:
            if not b in res:
                if not b in cost or cost[s]+c < cost[b]:
                    cost[b] = cost[s]+c
        elif s == b:
            if not a in res:
                if not a in cost or cost[s]+c < cost[a]:
                    cost[a] = cost[s]+c
    del cost[s]
    s = sorted(cost.items(), key=lambda x: x[1])[0][0]
    return f(s, cost, res)

while True:
    n, m = map(int, raw_input().split())
    if n == m == 0: break
    data = {}
    for i in range(n):
        a, b, c, t = map(int, raw_input().split())
        data[(a, b)] = [c, t]
    for i in range(int(raw_input())):
        s, g, r = map(int, raw_input().split())
        print f(s, {s:0}, [])

Submission status: Time Limit Exceeded

Solution code:
def f(s, cost, route):
    if s == g:
        return cost[g]
    route.append(s)
    for k, v in data.items():
        if s in k:
            a, b = k
            a, b = (a, b) if s == a else (b, a)
            c = v[0] if r == 0 else v[1]
            if not b in route:
                if not b in cost or cost[s]+c < cost[b]:
                    cost[b] = cost[s]+c
    del cost[s]
    s = sorted(cost.items(), key=lambda x: x[1])[0][0]
    return f(s, cost, route)

while True:
    n, m = map(int, raw_input().split())
    if n == m == 0: break
    data = {}
    for i in range(n):
        a, b, c, t = map(int, raw_input().split())
        data[(a, b)] = [c, t]
    for i in range(int(raw_input())):
        s, g, r = map(int, raw_input().split())
        print f(s, {s:0}, [])

Submission status: Time Limit Exceeded

Solution code:
### Warshall???Floyd ###

INF = float("inf")

#????????°V??§?????????: ??°??????????????????????????¢???INF?????????????????????????????¢???0
def init(V):
    d = [[INF] * V for i in range(V)]
    for i in range(V):
        d[i][i] = 0
    
    return d

#????????????????¨????
def wf(d, V):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

#for print debug
def print_matrix(m):
    for row in m:
        print('\t'.join(map(str, row)))

while True:
    #V:???????????°(m)??? E:????????°(n)
    E, V = map(int, input().split())
    
    if E == V == 0:
        break
    
    #?????????
    money = init(V)
    time = init(V)
    
    #??°??????????????? 
    for i in range(E):
        u, v, c, t = map(int, input().split())
        u -= 1; v -= 1;
        money[u][v] = money[v][u] = c
        time[u][v] = time[v][u] = t
    
    #????????????????¨????
    wf(money, V)
    wf(time, V)
    
    #?????????????????°
    K = int(input())
    
    #??????????????????????§£???
    for i in range(K):
        p, q, r = map(int, input().split())
        p -= 1; q -= 1
        if r == 0:
            print(money[p][q])
        else:
            print(time[p][q])

Submission status: Time Limit Exceeded

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():
    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)]
        for c in range(s):
            g_money[c][c] = 0
        g_time = deepcopy(g_money)

        # Set two maps.
        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

        # 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 - 1)
            print(ans[end - 1])


def main():
    algorithm()


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
""" Created by Jieyi on 7/28/16. """
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():
    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)]
        for c in range(s):
            g_money[c][c] = 0
        g_time = deepcopy(g_money)

        # Set two maps.
        for _ in range(n):
            x, y, money, time = map(int, input().split())
            x, y = x - 1, y - 1
            g_money[x][y], g_time[x][y] = money, 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 - 1)
            print(ans[end - 1])


def main():
    algorithm()


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
""" Created by Jieyi on 7/28/16. """
import sys


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():
    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)]
        for c in range(s):
            g_money[c][c] = 0
        g_time = g_money[:]

        # Set two maps.
        for _ in range(n):
            x, y, m, t = map(int, input().split())
            x, y = x - 1, y - 1
            g_money[x][y], g_time[x][y] = m, 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)
            ans = dijkstra(m, start - 1)
            print(ans[end - 1])


def main():
    algorithm()


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

while 1:
    n, m = map(int, raw_input().split())
    if n == m == 0: exit()
    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: Time Limit Exceeded

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
 
while 1:
    n, m = map(int, raw_input().split())
    if n == 0: break
    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: Time Limit Exceeded

Solution code:
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

while 1:
    n, m = map(int, raw_input().split())
    if n == 0: break
    adj =[[] for i in range(m)]
    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: Time Limit Exceeded

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

while 1:
    n, m = map(int, raw_input().split())
    if n == 0: break
    adj =[[] for i in xrange(m + 1)]
    for i in xrange(n):
        x, y, c, t = map(int, raw_input().split())
        adj[x].append([y, c, t])
        adj[y].append([x, c, t])
    n = input()
    for i in xrange(n):
        start, goal, flag = map(int, raw_input().split())
        print search(goal, [start], flag, 0, 0xffffffff)

Submission status: Time Limit Exceeded

Solution code:
import sys

def dijkstra(m, start, goal, matrix):
  defnode = {}
  cost = [sys.maxint for i in xrange(m+1)]
  cost[start] = 0
  node = start
  while True:
    defnode[node] = True
    for i in xrange(1, m+1):
      if i in defnode:
        continue
      if matrix[node][i] == sys.maxint:
        continue
      cost[i] = min(cost[i], cost[node]+matrix[node][i])
    minnode = sys.maxint
    mincost = sys.maxint
    for i in xrange(1, m+1):
      if i in defnode:
        continue
      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 for i in xrange(m+1)] for j in xrange(m+1)]
  time = [[sys.maxint for i in xrange(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: Time Limit Exceeded

Solution code:
import sys

def dijkstra(m, start, goal, matrix):
  defnode = {}
  cost = [sys.maxint] * (m+1)
  cost[start] = 0
  node = start
  while True:
    defnode[node] = True
    for i in xrange(1, m+1):
      if i in defnode:
        continue
      if matrix[node][i] == sys.maxint:
        continue
      cost[i] = min(cost[i], cost[node]+matrix[node][i])
    minnode = sys.maxint
    mincost = sys.maxint
    for i in xrange(1, m+1):
      if i in defnode:
        continue
      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: Time Limit Exceeded

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

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


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():
    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)

        # Set two maps.
        for _ in range(n):
            x, y, m, t = map(int, input().split())
            x, y = x - 1, y - 1
            g_money[x][y] = m
            g_time[x][y] = 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)
            ans = dijkstra(m, start - 1)
            print(ans[end - 1])


def main():
    algorithm()


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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


def floyd_warshall(path_map):
    """
    This is following to Floyd???Warshall algorithm. All path the shortest path.
    """

    for k in range(len(path_map)):
        for i in range(len(path_map)):
            for j in range(len(path_map)):
                if path_map[i][j] > path_map[i][k] + path_map[k][j]:
                    path_map[i][j] = path_map[i][k] + path_map[k][j]

    return path_map


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)

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

        g_money = floyd_warshall(g_money)
        g_time = floyd_warshall(g_time)

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


def main():
    algorithm()


if __name__ == '__main__':
    main()