Problem:


青春の片道切符

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

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

Input

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

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

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

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

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

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

Output

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

Sample Input

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

Output for the Sample Input

450
35



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


Sample output:
450
35

Submission status: Wrong Answer

Solution code:
import copy as c
CEIL = 1000000
lines=[]

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

    return minAnswer
'''

def main():
    input1 = input().split(' ')
    global lines
    lines=[[] for i in range(int(input1[1]))]
    for lineIndex in range(int(input1[0])):
        input2 = input().split(' ')
        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])
    for out in range(int(input())):
        input3 = input().split(' ')
        #print([].append(1))
        print(exploreMin(int(input3[0])-1, int(input3[1])-1, int(input3[2]), [], 0))
    input()

if __name__ == '__main__': main()

Submission status: Wrong Answer

Solution code:
import copy as c
CEIL = 1000000
lines=[]

def exploreMin(now, goal, mode, history, ans):
    #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])
        #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 main():
    input1 = input().split(' ')
    global lines
    lines=[[] for i in range(int(input1[1]))]
    for lineIndex in range(int(input1[0])):
        input2 = input().split(' ')
        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), end = a)
    input()

if __name__ == '__main__': main()

Submission status: Wrong Answer

Solution code:
import copy as c
CEIL = 2000000000
lines=[]

def exploreMin(now, goal, mode, history, ans):
    #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])
        #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 main():
    input1 = input().split(' ')
    global lines
    lines=[[] for i in range(int(input1[1]))]
    for lineIndex in range(int(input1[0])):
        input2 = input().split(' ')
        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), end = a)
    input()

if __name__ == '__main__': main()

Submission status: Wrong Answer

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
    break
print sys.stderr, "test"

Submission status: Wrong Answer

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

err = 100000

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

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
from sys import stdin

n,m = map(int,stdin.readline().split()) #n = the number of lines, m = the numer of stations

err = 100000

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

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

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

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

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

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

gomi = stdin.readline()
if gomi != "0 0\n":
    print "?????"

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N, M = map(int, raw_input().split())
mapCost = [[10000 for j in range(N)] for i in range(N)]
mapTime = [[10000 for j in range(N)] for i in range(N)]

for n in range(N):
	a,b,cost,time = map(int, raw_input().split())
	mapCost[a][b] = cost
	mapTime[a][b] = time
for n in range(N):
	mapCost[n][n] = 0
	mapTime[n][n] = 0

for k in range(N): # k = 間の値
	for i in range(N):
		for j in range(N):
			if mapCost[i][j] > (mapCost[i][k] + mapCost[k][j]):
				mapCost[i][j] = mapCost[i][k] + mapCost[k][j]
			if mapTime[i][j] > (mapTime[i][k] + mapTime[k][j]):
				mapTime[i][j] = mapTime[i][k] + mapTime[k][j]
K = input()
for k in range(K):
	p,q,r = map(int, raw_input().split())
	if r == 0:
		print mapCost[p][q]
	else :
		print mapTime[p][q]

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N, M = map(int, raw_input().split())
mapCost = [[10000 for j in range(N)] for i in range(N)]
mapTime = [[10000 for j in range(N)] for i in range(N)]

for n in range(N):
	a,b,cost,time = map(int, raw_input().split())
	mapCost[a-1][b-1] = cost
	mapTime[a-1][b-1] = time
for n in range(N):
	mapCost[n][n] = 0
	mapTime[n][n] = 0

for k in range(N): # k = 間の値
	for i in range(N):
		for j in range(N):
			if mapCost[i][j] > (mapCost[i][k] + mapCost[k][j]):
				mapCost[i][j] = mapCost[i][k] + mapCost[k][j]
			if mapTime[i][j] > (mapTime[i][k] + mapTime[k][j]):
				mapTime[i][j] = mapTime[i][k] + mapTime[k][j]

K = input()
for k in range(K):
	p,q,r = map(int, raw_input().split())
	if r == 0:
		print mapCost[p-1][q-1]
	else :
		print mapTime[p-1][q-1]

Submission status: Wrong Answer

Solution code:
inf = 2<<31
def solve(A,strt,goal):
	cost = [inf]*m
	visited = [False]*m
	cost[strt] = 0
	while 1:
		min = inf
		next = -1
		visited[strt] = True
		for i in range(m):
			if visited[i]: continue
			if A[strt][i]:
				d = cost[strt] + A[strt][i]
				if d < cost[i]:
					cost[i] = d
			if min > cost[i]:
				min = cost[i]
				next = i
		strt = next
		if next == -1: break
	return cost[goal]
    
while 1:
	n,m = map(int,raw_input().split())
	if n == 0: break
	T = [[0]*m for i in range(m)]
	C = [[0]*m for i in range(m)]
	for i in range(n):
		a,b,c,t = map(int,raw_input().split())
		T[a-1][b-1] = T[b-1][a-1] = t
		C[a-1][b-1] = T[b-1][a-1] = c
	for i in range(input()):
		a,b,q = map(int,raw_input().split())
		if q == 0:
			print solve(C,a-1,b-1)
		else:
			print solve(T,a-1,b-1)

Submission status: Wrong Answer

Solution code:
inf = 0x10101010
def solve(A,strt,goal):
	cost = [inf]*m
	visited = [False]*m
	cost[strt] = 0
	while 1:
		min = inf
		next = -1
		visited[strt] = True
		for i in range(m):
			if visited[i]: continue
			if A[strt][i]:
				d = cost[strt] + A[strt][i]
				if d < cost[i]:
					cost[i] = d
			if min > cost[i]:
				min = cost[i]
				next = i
		strt = next
		if next == -1: break
	return cost[goal]
    
while 1:
	n,m = map(int,raw_input().split())
	if n == 0: break
	T = [[0]*m for i in range(m)]
	C = [[0]*m for i in range(m)]
	for i in range(n):
		a,b,c,t = map(int,raw_input().split())
		T[a-1][b-1] = T[b-1][a-1] = t
		C[a-1][b-1] = T[b-1][a-1] = c
	for i in range(input()):
		a,b,q = map(int,raw_input().split())
		if q == 0:
			print solve(C,a-1,b-1)
		else:
			print solve(T,a-1,b-1)

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

Solution code:
max_ = 1001
n,m = list(map(int,input().split()))

costs = [[max_ for i in range(m+1)] for j in range(m+1)]
times = [[max_ for i in range(m+1)] for j in range(m+1)]

senro = [list(map(int,input().split())) for i in range(n)]
stack=[]



def solv(p,q):
    global costs
    global times
    global senro
    global stack
    if times[p][q] < max_:
        #最短経路算出済み
        return costs[p][q],times[p][q]

    if p == q:
        return 0,0

    min_cost = max_
    min_time = max_
    stack.append(p)

    for s in senro :
        if (s[0] == p or s[1] == p) :
            next_ = s[1] if s[0]==p else s[0]
            if next_ in stack: #経過済みは無視
                continue

            c,t = solv(next_,q)
            min_cost = min(c + s[2],min_cost)
            min_time = min(t + s[3],min_time)
    
    costs[p][q] = min_cost
    times[p][q] = min_time

    stack.pop()

    return min_cost,min_time

k = int(input())
for i in range(k):
    p,q,r = list(map(int,input().split()))
    solv(p,q)
    print(times[p][q] if r==1 else costs[p][q])

Submission status: Time Limit Exceeded

Solution code:
import sys

inf = sys.maxsize

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

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

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

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

def main():
    while True:
        n, m = map(int, input().split())
        if n == 0 and m == 0: return

        # 隣接リスト
        c_graph = [[] for _ in range(m)]
        t_graph = [[] for _ in range(m)]
    
        for i in range(n):
            a, b, cost, time = map(int, input().split())
            a -= 1
            b -= 1
            c_graph[a].append((b, cost))
            c_graph[b].append((a, cost))
            t_graph[a].append((b, time))
            t_graph[b].append((a, time))
            
        c_dist = [shortestPath(c_graph, s) for s in range(m)]
        t_dist = [shortestPath(t_graph, s) for s in range(m)]
            
        k = int(input())
        for i in range(k):
            p, q, r = map(int, input().split())
            p -= 1
            q -= 1
            if r == 0:
                print(c_dist[p][q])
            else:
                print(t_dist[p][q])

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq as h

inf = sys.maxsize

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

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

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

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

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

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

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

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

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

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

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

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

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

    return dist

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq as h

inf = sys.maxsize

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

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

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

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

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

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

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

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

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

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

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

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

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

    return dist

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq as h

inf = sys.maxsize

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

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

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

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

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

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

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

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

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

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

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

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

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

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

        k = int(input())
        for i in range(k):
            p, q, r = map(int, input().split())
            p-=1
            q-=1
            if p > q:
                p, q = q, p
            if r == 0:
                print(shortestPath1(cgraph, p, q))
            else:
                print(shortestPath1(tgraph, p, q))
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq as h

inf = sys.maxsize

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

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

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

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

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

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

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

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

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

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

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

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

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

    return dist

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

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

Submission status: Time Limit Exceeded

Solution code:
inf = 0x10101010
def solve(A, strt):
	cost = [inf]*m  
	visited = [False]*m
	cost[strt] = 0
	while 1:
		min = inf 
		next = -1   
		visited[strt] = True 
		for i in range(m):
			if visited[i]: continue
			if A[strt][i]:
				d = cost[strt] + A[strt][i]
				if d < cost[i]:
					cost[i] = d
			if cost[i] < min:
				min = cost[i]
				next = i
		strt = next 
		if next == -1: break
	return cost
						
while 1:
	n,m = map(int, raw_input().split())


	if n == 0:
		break
	T = [[0]*m for i in range(m)]
	C = [[0]*m for i in range(m)]

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

Submission status: Time Limit Exceeded

Solution code:
inf = 0x10101010
def solve(A, strt):
	cost = [inf]*m  
	visited = [False]*m
	cost[strt] = 0
	while 1:
		min = inf 
		next = -1   
		visited[strt] = True 
		for i in range(m):
			if visited[i]: continue
			if A[strt][i]:
				d = cost[strt] + A[strt][i]
				if d < cost[i]:
					cost[i] = d
			if cost[i] < min:
				min = cost[i]
				next = i
		strt = next 
		if next == -1: break
	return cost
						
while 1:
	n,m = map(int, raw_input().split())
	if n == 0:break
	T = [[0]*m for i in range(m)]
	C = [[0]*m for i in range(m)]
	for i in range(n):
		a, b, c, t = map(int, raw_input().split()) 
		T[a-1][b-1] = T[b-1][a-1] = t 
		C[a-1][b-1] = C[b-1][a-1] = c
	TS = [solve(T, i) for i in range(m)]
	CS = [solve(C, i) for i in range(m)]
	for i in range(input()):
		a, b, q = map(int, raw_input().split())
		if q == 0:
			print CS[a-1][b-1]
		else:
			print TS[a-1][b-1]

Submission status: 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())
    for i in range(k):
        p, q, r = map(int, f.readline().split())
        dist = dijkstra(graph, m + 1, p, r)
        print(dist[q])