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 sys
from heapq import heappush, heappop


R=lambda:map(int,raw_input().split())
MAX_VAL = 10**8
class Node:
    def __init__(self, index):
        self.index = index
        self.to = []
        self.cost = []
        self.time = []
        self.visited = False
        self.c,self.t = MAX_VAL, MAX_VAL
        self.prev = None

while 1:
    n,m = R()
    if not (n or m): break
    nodes = [Node(i) for i in xrange(m+1)]
    for i in xrange(1,n+1):
        a,b,cost,time = R()
        nodes[a].to.append(b)
        nodes[a].cost.append(cost)
        nodes[a].time.append(time)

    k = int(raw_input())
    for i in xrange(k):
        for j in xrange(1, len(nodes)):
            nodes[j].c = MAX_VAL
            nodes[j].t = MAX_VAL
            nodes[j].visited = False
            nodes[j].prev = None
        start,end,typ = R()
        nodes[start].c = 0
        nodes[start].t = 0
        nodes[start].prev = start
        q = []
        heappush(q, nodes[start])
        while not(q == []):
            node = heappop(q)
            #print sys.stderr, node
            if node.visited is True: continue
            node.visited = True
            for i in xrange(len(node.to)):
                to = node.to[i]
                if typ is 0:
                    cost = node.c + node.cost[i]
                    #print sys.stderr, to,cost
                    if cost < nodes[to].c:
                        nodes[to].c = cost
                        nodes[to].prev = node.index
                        heappush(q, nodes[to])
                elif typ is 1:
                    time = node.t + node.time[i]
                    #print sys.stderr, to,time
                    if time < nodes[to].t:
                        nodes[to].t = time
                        nodes[to].prev = node.index
                        heappush(q, nodes[to])

##        path = []
##        index = end
##        while (index is not start):
##            path.append(str(index))
##            index = nodes[index].prev
##        path.append(str(start))
        if typ is 0: print nodes[end].c
        else: print nodes[end].t

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappush, heappop

R=lambda:map(int,raw_input().split())
MAX_VAL = 10**7
class Node:
    def __init__(self, index):
        self.index = index
        self.to = []
        self.cost = []
        self.time = []
        self.visited = False
        self.c,self.t = MAX_VAL, MAX_VAL
        #self.prev = None

while 1:
    n,m = R()
    if not (n or m): break
    nodes = [Node(i) for i in xrange(m+1)]
    for i in xrange(1,n+1):
        a,b,cost,time = R()
        nodes[a].to.append(b)
        nodes[a].cost.append(cost)
        nodes[a].time.append(time)

    k = int(raw_input())
    for i in xrange(k):
        for j in xrange(1, len(nodes)):
            nodes[j].c = MAX_VAL
            nodes[j].t = MAX_VAL
            nodes[j].visited = False
            #nodes[j].prev = None
        start,end,typ = R()
        nodes[start].c = 0
        nodes[start].t = 0
        #nodes[start].prev = start
        q = []
        heappush(q, nodes[start])
        while not(q == []):
            node = heappop(q)
            #print sys.stderr, node
            if node.visited is True: continue
            node.visited = True
            for i in xrange(len(node.to)):
                to = node.to[i]
                if typ is 0:
                    cost = node.c + node.cost[i]
                    #print sys.stderr, to,cost
                    if cost < nodes[to].c:
                        nodes[to].c = cost
                        #nodes[to].prev = node.index
                        heappush(q, nodes[to])
                elif typ is 1:
                    time = node.t + node.time[i]
                    #print sys.stderr, to,time
                    if time < nodes[to].t:
                        nodes[to].t = time
                        #nodes[to].prev = node.index
                        heappush(q, nodes[to])

##        path = []
##        index = end
##        while (index is not start):
##            path.append(str(index))
##            index = nodes[index].prev
##        path.append(str(start))
        if typ is 0: print nodes[end].c
        else: print nodes[end].t

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappush, heappop
 
 
R=lambda:map(int,raw_input().split())
MAX_VAL = 10**8
class Node:
    def __init__(self, index):
        self.index = index
        self.to = []
        self.cost = []
        self.time = []
        self.visited = False
        self.c,self.t = MAX_VAL, MAX_VAL
        self.prev = None

    def __cmp__(self, other):
        if self.c == MAX_VAL:
            return self.t - other.t
        else:
            return self.c - other.c
 
while 1:
    n,m = R()
    if not (n or m): break
    nodes = [Node(i) for i in xrange(m+1)]
    for i in xrange(1,n+1):
        a,b,cost,time = R()
        nodes[a].to.append(b)
        nodes[a].cost.append(cost)
        nodes[a].time.append(time)
    costs=[0 for i in xrange(m+1)]
    k = int(raw_input())
    for i in xrange(k):
        for j in xrange(1, len(nodes)):
            nodes[j].c = MAX_VAL
            nodes[j].t = MAX_VAL
            nodes[j].visited = False
            nodes[j].prev = None
        start,end,typ = R()
        nodes[start].c = 0
        nodes[start].t = 0
        nodes[start].prev = start
        q = []
        heappush(q, nodes[start])
        while not(q == []):
            node = heappop(q)
            print sys.stderr, node.index,node.c,node.t,node.visited
            #print sys.stderr, node
            if node.visited is True: continue
            node.visited = True
            for i in xrange(len(node.to)):
                to = node.to[i]
                if typ is 0:
                    cost = node.c + node.cost[i]
                    #print sys.stderr, to,cost
                    if cost < nodes[to].c:
                        nodes[to].c = cost
                        nodes[to].prev = node.index
                        heappush(q, nodes[to])
                elif typ is 1:
                    time = node.t + node.time[i]
                    #print sys.stderr, to,time
                    if time < nodes[to].t:
                        nodes[to].t = time
                        nodes[to].prev = node.index
                        heappush(q, nodes[to])
 
##        path = []
##        index = end
##        while (index is not start):
##            path.append(str(index))
##            index = nodes[index].prev
##        path.append(str(start))
        if typ is 0: print nodes[end].c
        else: print nodes[end].t

Submission status: Time Limit Exceeded

Solution code:
def doIt():
    (n, m) = map(int, raw_input().split())
    while(0 < n + m):
        mmax = 1.0e9
        costs = [[mmax for j in range(m)] for i in range(m)]
        times = [[mmax for j in range(m)] for i in range(m)]
        for i in range(m): costs[i][i] = times[i][i] = 0
        for i in range(n):
            (a, b, cost, time) = map(int, raw_input().split())
            a -= 1
            b -= 1
            costs[a][b] = costs[b][a] = cost
            times[a][b] = times[b][a] = time
        #Warshall-Floyd Algorithm
        for k in range(m):
            for i in range(m):
                for j in range(m):
                    costs[i][j] = costs[j][i] = min(costs[i][j], costs[i][k] + costs[k][j])
                    times[i][j] = times[j][i] = min(times[i][j], times[i][k] + times[k][j])
                    #pass
        k = input()
        for i in range(k):
            (p, q, r) = map(int, raw_input().split())
            p -= 1
            q -= 1
            if(r == 0): print costs[p][q]
            else: print times[p][q]
        (n, m) = map(int, raw_input().split())
        
doIt()

Submission status: Time Limit Exceeded

Solution code:
def doIt():
    (n, m) = map(int, raw_input().split())
    while(0 < n + m):
        mmax = 1.0e9
        costs = [[mmax for j in range(m)] for i in range(m)]
        times = [[mmax for j in range(m)] for i in range(m)]
        for i in range(m): costs[i][i] = times[i][i] = 0
        for i in range(n):
            (a, b, cost, time) = map(int, raw_input().split())
            a -= 1
            b -= 1
            costs[a][b] = costs[b][a] = cost
            times[a][b] = times[b][a] = time
        #Warshall-Floyd Algorithm
        for k in range(m):
            for i in range(m):
                for j in range(i+1, m):
                    costs[i][j] = costs[j][i] = min(costs[i][j], costs[i][k] + costs[k][j])
                    times[i][j] = times[j][i] = min(times[i][j], times[i][k] + times[k][j])
                    #pass
        k = input()
        for i in range(k):
            (p, q, r) = map(int, raw_input().split())
            p -= 1
            q -= 1
            if(r == 0): print costs[p][q]
            else: print times[p][q]
        (n, m) = map(int, raw_input().split())
        
doIt()

Submission status: Time Limit Exceeded

Solution code:
def floyd(P):
    for k in range(m):
        for i in range(m):
            for j in range(m):
                P[i][j]=min(P[i][j],P[i][k]+P[k][j])

while True:
    n,m=map(int,raw_input().split())
    if n==m==0:break
    INF=1e10
    C=[[INF]*m for i in range(m)]
    T=[[INF]*m for i in range(m)]
    for i in range(m):
        C[i][i]=0
        T[i][i]=0
    for i in range(n):
        a,b,cost,time=map(int,raw_input().split())
        C[a-1][b-1]=cost
        C[b-1][a-1]=cost
        T[a-1][b-1]=time
        T[b-1][a-1]=time
    floyd(C)
    floyd(T)
    k=input()
    for i in range(k):
        p,q,r=map(int,raw_input().split())
        print C[p-1][q-1] if r==0 else T[p-1][q-1]

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
INF = 1 << 30
while True:
    n, m = map(int, raw_input().split()) 
    if n | m == 0:
        break
    C = [[INF] * (m + 1) for _ in xrange(n+1)]
    T = [[INF] * (m + 1) for _ in xrange(n+1)]
    for _ in xrange(n):
        a, b, c, t = map(int, raw_input().split())
        C[a][b] = C[b][a] = c
        T[a][b] = T[b][a] = t
    for k, i, j in product(xrange(m + 1), repeat = 3):
        C[i][j] = min(C[i][j], C[i][k] + C[k][j])
        T[i][j] = min(T[i][j], T[i][k] + T[k][j])    
    A = (C, T)
    for _ in xrange(input()):
        p, q, r = map(int, raw_input().split())
        print A[r][p][q]

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
INF = 1 << 29
while True:
    n, m = map(int, raw_input().split()) 
    if n | m == 0:
        break
    C = [[INF] * (m + 1) for _ in xrange(n+1)]
    T = [[INF] * (m + 1) for _ in xrange(n+1)]
    for _ in xrange(n):
        a, b, c, t = map(int, raw_input().split())
        C[a][b] = C[b][a] = c
        T[a][b] = T[b][a] = t
    for k, i, j in product(xrange(m + 1), repeat = 3):
        C[i][j] = min(C[i][j], C[i][k] + C[k][j])
        T[i][j] = min(T[i][j], T[i][k] + T[k][j])    
    A = (C, T)
    for _ in xrange(input()):
        p, q, r = map(int, raw_input().split())
        print A[r][p][q]

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
INF = 1 << 29
while True:
    n, m = map(int, raw_input().split()) 
    if n | m == 0:
        break
    C = [[INF] * (m + 1) for _ in xrange(m + 1)]
    T = [[INF] * (m + 1) for _ in xrange(m + 1)]
    for _ in xrange(n):
        a, b, c, t = map(int, raw_input().split())
        C[a][b] = C[b][a] = c
        T[a][b] = T[b][a] = t
    for k, i, j in product(xrange(m + 1), repeat = 3):
        C[i][j] = min(C[i][j], C[i][k] + C[k][j])
        T[i][j] = min(T[i][j], T[i][k] + T[k][j])    
    A = (C, T)
    for _ in xrange(input()):
        p, q, r = map(int, raw_input().split())
        print A[r][p][q]

Submission status: Time Limit Exceeded

Solution code:
import heapq
N, M = 3001, 101

def dijkstra(s, t, G):
    visited = [False] * (M + 1)
    pq = [(0,s)]
    while True:
        cost, cur = heapq.heappop(pq)
        if cur == t:
            return cost
        if visited[cur]:
            continue
        visited[cur] = True
        for nex in filter(lambda i:G[cur][i] != -1 and not visited[i], xrange(M+1)):
            heapq.heappush(pq, (cost + G[cur][nex], nex))

while True:
    N, M = map(int, raw_input().split())
    if N | M == 0:
        break
    C = [[-1] * (M + 1) for _ in xrange(M + 1)]
    T = [[-1] * (M + 1) for _ in xrange(M + 1)]
    for _ in xrange(N):
        a, b, c, t = map(int, raw_input().split())
        C[a][b] = C[b][a] = c
        T[a][b] = T[b][a] = t
    A = (C, T)
    for _ in xrange(input()):
        p, q, r = map(int, raw_input().split())
        print dijkstra(p, q, A[r])

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
INF = 1 << 20
while True:
    n, m = map(int, raw_input().split()) 
    if n | m == 0:
        break
    C = [[INF] * (m + 1) for _ in xrange(m + 1)]
    T = [[INF] * (m + 1) for _ in xrange(m + 1)]
    for _ in xrange(n):
        a, b, c, t = map(int, raw_input().split())
        C[a][b] = C[b][a] = c
        T[a][b] = T[b][a] = t
    for k, i, j in product(xrange(m + 1), repeat = 3):
        C[i][j] = min(C[i][j], C[i][k] + C[k][j])
        T[i][j] = min(T[i][j], T[i][k] + T[k][j])    
    A = (C, T)
    for _ in xrange(input()):
        p, q, r = map(int, raw_input().split())
        print A[r][p][q]

Submission status: Time Limit Exceeded

Solution code:
INF = 1 << 20
while True:
    n, m = map(int, raw_input().split()) 
    if n | m == 0:
        break
    C = [[INF] * (m + 1) for _ in xrange(m + 1)]
    T = [[INF] * (m + 1) for _ in xrange(m + 1)]
    for _ in xrange(n):
        a, b, c, t = map(int, raw_input().split())
        C[a][b] = C[b][a] = c
        T[a][b] = T[b][a] = t
    for k in xrange(m + 1):
        for i in xrange(m + 1):
            for j in xrange(m + 1):
                C[i][j] = min(C[i][j], C[i][k] + C[k][j])
                T[i][j] = min(T[i][j], T[i][k] + T[k][j])    
    A = (C, T)
    for _ in xrange(input()):
        p, q, r = map(int, raw_input().split())
        print A[r][p][q]

Submission status: Time Limit Exceeded

Solution code:
import heapq
INF = 1 << 20
N, M = 3001, 101

def dijkstra(s, G):
    visited = [False] * (M + 1)
    visited[0] = True
    d = [-1] * (M + 1)
    pq = [(0,s)]
    while not all(visited):
        cost, cur = heapq.heappop(pq)
        if visited[cur]:
            continue
        visited[cur] = True
        d[cur] = cost
        for nex in filter(lambda i:G[cur][i] != -1, xrange(1, M + 1)):
            heapq.heappush(pq, (cost + G[cur][nex], nex))
    return d
            
while True:
    N, M = map(int, raw_input().split())
    if N | M == 0:
        break
    C = [[-1] * (M + 1) for _ in xrange(M + 1)]
    T = [[-1] * (M + 1) for _ in xrange(M + 1)]
    for _ in xrange(N):
        a, b, c, t = map(int, raw_input().split())
        C[a][b] = C[b][a] = c
        T[a][b] = T[b][a] = t
    for s in xrange(1, M + 1):
        C[s] = dijkstra(s,C)
        T[s] = dijkstra(s,T)
    A = (C, T)
    for _ in xrange(input()):
        p, q, r = map(int, raw_input().split())
        print A[r][p][q]

Submission status: Time Limit Exceeded

Solution code:
import heapq
INF = 1 << 20
N, M = 3001, 101

def dijkstra(s, G):
    visited = [False] * (M + 1)
    visited[0] = True
    d = [-1] * (M + 1)
    pq = [(0,s)]
    while not all(visited):
        cost, cur = heapq.heappop(pq)
        if visited[cur]:
            continue
        visited[cur] = True
        d[cur] = cost
        for nex in filter(lambda i:G[cur][i] != -1, xrange(1, M + 1)):
            heapq.heappush(pq, (cost + G[cur][nex], nex))
    return d
            
while True:
    N, M = map(int, raw_input().split())
    if N | M == 0:
        break
    C = [[-1] * (M + 1) for _ in xrange(M + 1)]
    T = [[-1] * (M + 1) for _ in xrange(M + 1)]
    for _ in xrange(N):
        a, b, c, t = map(int, raw_input().split())
        C[a][b] = C[b][a] = c
        T[a][b] = T[b][a] = t
    A = (C, T)
    checked = [[False] * (M + 1) for  _ in xrange(2)]
    for _ in xrange(input()):
        p, q, r = map(int, raw_input().split())
        if not checked[r][p]:
            A[r][p] = dijkstra(p, A[r])
            checked[r][p] = True
        print A[r][p][q]

Submission status: Time Limit Exceeded

Solution code:
import heapq
INF = 1 << 20
N, M = 3001, 101

def dijkstra(s, t, G):
    visited = [False] * (M + 1)
    visited[0] = True
    pq = [(0,s)]
    while True:
        cost, cur = heapq.heappop(pq)
        if visited[cur]:
            continue
        if cur == t:
            return cost
        visited[cur] = True
        for nex in xrange(1, M + 1):
            heapq.heappush(pq, (cost + G[cur][nex], nex))
    return -1
            
while True:
    N, M = map(int, raw_input().split())
    if N | M == 0:
        break
    C = [[INF] * (M + 1) for _ in xrange(M + 1)]
    T = [[INF] * (M + 1) for _ in xrange(M + 1)]
    for _ in xrange(N):
        a, b, c, t = map(int, raw_input().split())
        C[a][b] = C[b][a] = c
        T[a][b] = T[b][a] = t
    A = (C, T)
    checked = [[[False] * (M + 1) for  _ in xrange(M + 1)] for _ in xrange(2)]
    for _ in xrange(input()):
        p, q, r = map(int, raw_input().split())
        if not checked[r][p][q]:
            A[r][p][q] = dijkstra(p, q, A[r])
            checked[r][p][q] = True
        print A[r][p][q]

Submission status: Time Limit Exceeded

Solution code:
import heapq
INF = 1 << 20
N, M = 3001, 101

def dijkstra(s, t, G):
    visited = [False] * (M + 1)
    visited[0] = True
    pq = [(0,s)]
    while True:
        cost, cur = heapq.heappop(pq)
        if visited[cur]:
            continue
        if cur == t:
            return cost
        visited[cur] = True
        for nex in filter(lambda x:G[cur][x] != -1 and not visited[x], xrange(1, M + 1)):
            heapq.heappush(pq, (cost + G[cur][nex], nex))
    return -1
            
while True:
    N, M = map(int, raw_input().split())
    if N | M == 0:
        break
    C = [[-1] * (M + 1) for _ in xrange(M + 1)]
    T = [[-1] * (M + 1) for _ in xrange(M + 1)]
    for _ in xrange(N):
        a, b, c, t = map(int, raw_input().split())
        C[a][b] = C[b][a] = c
        T[a][b] = T[b][a] = t
    A = (C, T)
    checked = [[[False] * (M + 1) for  _ in xrange(M + 1)] for _ in xrange(2)]
    for _ in xrange(input()):
        p, q, r = map(int, raw_input().split())
        if not checked[r][p][q]:
            A[r][p][q] = dijkstra(p, q, A[r])
            checked[r][p][q] = True
        print A[r][p][q]

Submission status: Time Limit Exceeded

Solution code:

INF = 1000000000

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

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

Submission status: Time Limit Exceeded

Solution code:

INF = 1000000000

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

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

Submission status: Time Limit Exceeded

Solution code:

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

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

Submission status: Time Limit Exceeded

Solution code:

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

    if v == e:
      return d[e]
    done[v] = True
    
    i = 0
    while i < V:
      d[i] = min(d[i], d[v] + cost[v][i][r])
      i += 1

while True:
  cost = [[[INF for k in range(2)] for j in range(100)] for i in range(100)]
  E, V = map(int, raw_input().split())
  if not E:
    break
  i = 0
  while i < E:
    a, b, c, d = map(int, raw_input().split())
    a -= 1
    b -= 1
    cost[a][b][0] = cost[b][a][0] = c
    cost[a][b][1] = cost[b][a][1] = d
    i += 1

  k = input()
  i = 0
  while i < k:
    p, q, r = map(int, raw_input().split())
    p -= 1
    q -= 1
    print dj(p, q, r)
    i += 1

Submission status: Time Limit Exceeded

Solution code:

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

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

Submission status: Time Limit Exceeded

Solution code:

from copy import deepcopy
INF = 1000000000
def dj(s, e, r):
  d = infPre[:]
  done = zeroPre[:]
  d[s] = 0
  while True:
    v = -1
    for i in VL:
      if not done[i] and (v == -1 or d[i] < d[v]):
        v = i
    if v == e:
      return d[e]
    done[v] = True
    for i in VL:
      d[i] = min(d[i], d[v] + cost[v][i][r])

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

Submission status: Time Limit Exceeded

Solution code:

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

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

Submission status: Time Limit Exceeded

Solution code:

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

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

Submission status: Time Limit Exceeded

Solution code:

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

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

Submission status: Time Limit Exceeded

Solution code:

INF = 1000000000
L100 = range(100)
infPre = [INF] * 100
zeroPre = [0] * 100
while True:
  cost = [[[INF for k in range(2)] for j in L100] for i in L100]
  E, V = map(int, raw_input().split())
  VL = range(V)
  if not E:
    break
  for i in range(E):
    a, b, c, d = map(int, raw_input().split())
    a -= 1
    b -= 1
    cost[a][b][0] = cost[b][a][0] = c
    cost[a][b][1] = cost[b][a][1] = d
  k = input()
  for i in range(k):
    p, q, r = map(int, raw_input().split())
    p -= 1
    q -= 1
    
    #dijkstra method
    d = infPre[:]
    done = zeroPre[:]
    d[p] = 0
    while True:
      v = -1
      for i in VL:
        if not done[i] and (v == -1 or d[i] < d[v]):
          v = i
      if v == q:
        print d[q]
        break
      done[v] = True
      for i in VL:
        d[i] = min(d[i], d[v] + cost[v][i][r])

Submission status: Time Limit Exceeded

Solution code:

def solve():
  INF = 1000000000
  L100 = xrange(100)
  infPre = [INF] * 100
  zeroPre = [0] * 100
  while True:
    cost = [[[INF for k in range(2)] for j in L100] for i in L100]
    E, V = map(int, raw_input().split())
    VL = xrange(V)
    if not E:
      break
    for i in xrange(E):
      a, b, c, d = map(int, raw_input().split())
      a -= 1
      b -= 1
      cost[a][b][0] = cost[b][a][0] = c
      cost[a][b][1] = cost[b][a][1] = d
    k = input()
    for i in xrange(k):
      p, q, r = map(int, raw_input().split())
      p -= 1
      q -= 1
    
      d = infPre[:]
      done = zeroPre[:]
      d[p] = 0
      while True:
        v = -1
        for i in VL:
          if not done[i] and (v == -1 or d[i] < d[v]):
            v = i
        if v == q:
          print d[q]
          break
        done[v] = True
        for i in VL:
          d[i] = min(d[i], d[v] + cost[v][i][r])

solve()

Submission status: Time Limit Exceeded

Solution code:
INF = 10**7

class C:
	def __init__(self,i):
		self.i=i
		self.tp=INF
		self.tt=INF

class W:
	def __init__(self,i,ac,bc,p,t):
		self.i=i
		self.ac=ac
		self.bc=bc
		self.p=p
		self.t=t

def readLineAsTupleOfInt():
	return tuple(map(int,raw_input().split()))

def dijk(argCs,argCi_cws,startCi,endCi,p):
	endC=argCs[endCi]
	cs=argCs[:]
	ci_cws=argCi_cws[:]
	tp="t"+p
	for c in cs:
		setattr(c,tp, 0 if c.i == startCi else INF)
	while(len(cs)!=0):
		cs.sort(key = lambda c: getattr(c,tp))
		kc = cs.pop(0)
		kctp=getattr(kc,tp)
		kcws=ci_cws[kc.i]
		for kcw in kcws:
			setattr(kcw.bc,tp, min(getattr(kcw.bc,tp),kctp+getattr(kcw,p)))
	return getattr(endC,tp)

while True:
	inp=readLineAsTupleOfInt()
	if inp==(0,0): break
	wl,cl=inp

	cs = [C(ci) for ci in xrange(cl)]
	ws = []
	ci_cws = [[] for wi in xrange(cl)]

	for wi in xrange(wl):
		waci_,wbci_,wp,wt = readLineAsTupleOfInt()
		waci = waci_ - 1
		wbci = wbci_ - 1
		wac = cs[waci]
		wbc = cs[wbci]
		w = W(wi,wac,wbc,wp,wt)
		ws.append(w)
		ci_cws[waci].append(w)
		wac,wbc = wbc,wac
		waci,wbci = wbci,waci
		w = W(wi,wac,wbc,wp,wt)
		ws.append(w)
		ci_cws[waci].append(w)



	ql = int(raw_input())
	for qi in xrange(ql):
		qStartCi_, qEndCi_, qP = readLineAsTupleOfInt()
		qStartCi = qStartCi_ - 1
		qEndCi = qEndCi_ - 1
		qP = ("p","t")[qP]
		print dijk(cs,ci_cws,qStartCi,qEndCi,qP)