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:
cost_ans = []
time_ans = []

def set_ans(cost , time):
    cost_ans.append(cost)
    time_ans.append(time)

class Sta(object):
    """station"""
    def __init__(self, station_name):
        super(Sta, self).__init__()
        self.station_name = station_name
        self.route = []

    def add_route(self, route):
        self.route.append(route)



class Route(object):
    """route"""
    def __init__(self, cost, time, next_station):
        super(Route, self).__init__()
        self.time = time
        self.cost = cost
        self.next_station = next_station

def search_route(now_station, gool_station, cost, time):
    """search route"""

    if now_station.station_name == gool_station.station_name:
        set_ans(cost, time)
        return

    elif len(now_station.route) == 0:
        return

    for r in now_station.route:
        search_route(
                r.next_station,
                gool_station,
                cost + r.cost,
                time + r.time)
def main():

    while True:
        set_ans([],[])
        n,m = map(int, raw_input().split())
        if n == 0 and m == 0:
            return

        stations = [Sta(x) for x in xrange(1,m+1) ]

        for i in xrange(n):
            a, b, cost, time = map(int, raw_input().split())
            tmp = Route(cost, time, stations[b-1])
            stations[a-1].add_route(tmp)

        k = input()
        for i in xrange(k):
            p, q, r = map(int, raw_input().split())
            search_route(stations[p-1], stations[q-1], 0, 0)
            if r == 0:
                print(min(cost_ans))
            else:
                print(min(time_ans))



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
inf = 0x101010
def floyd(P,m):
	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 1:
	n,m = map(int,raw_input().split())
	if n == 0: break
	C = [[inf]*n for i in range(m)]
	T = [[inf]*n 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,c,t = map(int,raw_input().split())
		C[a-1][b-1] = C[b-1][a-1] = c
		T[a-1][b-1] = T[b-1][a-1] = t
	floyd(C,m);floyd(T,m)
	for i in range(input()):
		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:
max_ = 1001
def solv(p,q):
    global costs
    global times
    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

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

    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=[]

    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:
max_ = 1001
def solv(p,q):
    global costs
    global times
    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


def froid():
    global costs
    global times
    global m
    for s in senro:
        costs[s[0]][s[1]] = s[2]
        costs[s[1]][s[0]] = s[2]
        times[s[0]][s[1]] = s[3]
        times[s[1]][s[0]] = s[3]

    for k in range(1,m+1):
        for i in range(1,m+1):
            for j in range(1,m+1):
                costs[i][j] = min(costs[i][j],costs[i][k] + costs[k][j])
                times[i][j] = min(times[i][j],times[i][k] + times[k][j])
while True:
    n,m = list(map(int,input().split()))
    if n == 0 and m == 0:
        break

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

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

Submission status: Time Limit Exceeded

Solution code:
max_ = 1000000
#def solv(p,q):
    #global costs
    #global times
    #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

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

    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)]
    for i in range(n):
        s = list(map(int,input().split()))
        costs[s[0]][s[1]] = s[2]
        costs[s[1]][s[0]] = s[2]
        times[s[0]][s[1]] = s[3]
        times[s[1]][s[0]] = s[3]

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

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

Submission status: Accepted

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 min > cost[i]:
                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: Accepted

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 min > cost[i]:
                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: Accepted

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 min > cost[i]:	
				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: Accepted

Solution code:
import heapq
import sys
from collections import defaultdict

def dijkstra(graph, size, start):
    d = [float('inf')] * size
    d[start] = 0
    q = [(0, start)]
    while len(q):
        du, u = heapq.heappop(q)
        for length, v in graph[u]:
            if d[v] > du + length:
                d[v] = du + length
                heapq.heappush(q, (d[v], v))
    return d

f = sys.stdin

while True:
    n, m = map(int, f.readline().split())
    if n == 0:
        break
    abct = [map(int, f.readline().split()) for _ in range(n)]
    d = [defaultdict(list), defaultdict(list)]
    
    for ai, bi, ci, ti in abct:
        ai -= 1
        bi -= 1
        d[0][ai].append((ci, bi))
        d[0][bi].append((ci, ai))
        d[1][ai].append((ti, bi))
        d[1][bi].append((ti, ai))
    
    dist = {}
    for i in range(int(f.readline())):
        p, q, r = map(int, f.readline().split())
        p -= 1
        q -= 1
        try:
            print(dist[(q,r)][p])
        except KeyError:
            try:
                print(dist[(p,r)][q])
            except:
                dist[(p,r)] = dijkstra(d[r], m, p)
                print(dist[(p,r)][q])

Submission status: Accepted

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(i,m+1):
                    if C[i][j]>C[i][k]+C[k][j]:
                        C[i][j]=C[i][k]+C[k][j]
                        C[j][i]=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]
                        T[j][i]=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: Accepted

Solution code:
import heapq

def dijkstra(s,g,m):
    global pq
    global d
    color=[0]*n
    d=[float('inf')]*n
    d[s]=0
    heapq.heappush(pq,[0,s])
    while len(pq)!=0:
        t,u=heapq.heappop(pq)
        color[u]=2
        if d[u]<t:
            continue
        for v in g[u]:
            if color[v]!= 2:
                if d[u]+m[u][v]<d[v]:
                    d[v]=d[u]+m[u][v]
                    color[v]=1
                    heapq.heappush(pq,[d[v],v])

while 1:
    pq=[]
    n,m=map(int,raw_input().split())
    g=[[] for _ in xrange(m)]
    cost=[[0]*m for _ in xrange(m)]
    time=[[0]*m for _ in xrange(m)]
    if n==m==0:
        break
    for i in xrange(n):
        a,b,c,t=map(int,raw_input().split())
        g[a-1].append(b-1)
        g[b-1].append(a-1)
        cost[a-1][b-1]=c
        cost[b-1][a-1]=c
        time[a-1][b-1]=t
        time[b-1][a-1]=t
    k=input()
    for i in xrange(k):
        p,q,r=map(int,raw_input().split())
        if r==0:
            dijkstra(p-1,g,cost)
            print(d[q-1])
        else:
            dijkstra(p-1,g,time)
            print(d[q-1])

Submission status: Accepted

Solution code:
import sys

def dijkstra(m, start, goal, matrix):
  defnode = [False] * (m+1)
  cost = [sys.maxint] * (m+1)
  cost[start] = 0
  node = start
  while True:
    defnode[node] = True
    for i in xrange(1, m+1):
      if defnode[i]:
        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 defnode[i]:
        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: Accepted

Solution code:
from heapq import heappop, heappush


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

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

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

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


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

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

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

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

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


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

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


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

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

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

Submission status: Accepted

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

def main():
  
  while True:
    n, m = map(int, input().split())
    
    if not n:
      break
    
    cost_edges = [[] for _ in range(m)]
    time_edges = [[] for _ in range(m)]
  
    for _ in range(n):
      a, b, c, t = map(int, input().split())
      cost_edges[a - 1].append((c, b - 1))
      cost_edges[b - 1].append((c, a - 1))
      time_edges[a - 1].append((t, b - 1))
      time_edges[b - 1].append((t, a - 1))
    
    k = int(input())
  
    for _ in range(k):
      start, goal, r = map(int ,input().split())
      start -= 1
      goal -= 1
      
      if r:
        edges = time_edges
      else:
        edges = cost_edges
  
      que = [(0, start)]
      visited = [False for _ in range(m)]
      
      while que:
        score, station = hpop(que)
        visited[station] = True
        
        if station == goal:
          print(score)
          break
  
        for c, to_station in edges[station]:
          if not visited[to_station]:
            hpush(que, (score + c, to_station))

main()

Submission status: Accepted

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

def main():
  
  while True:
    n, m = map(int, input().split())
    
    if not n:
      break
    
    cost_edges = [[] for _ in range(m)]
    time_edges = [[] for _ in range(m)]
  
    for _ in range(n):
      a, b, c, t = map(int, input().split())
      cost_edges[a - 1].append((c, b - 1))
      cost_edges[b - 1].append((c, a - 1))
      time_edges[a - 1].append((t, b - 1))
      time_edges[b - 1].append((t, a - 1))
    
    k = int(input())
  
    for _ in range(k):
      start, goal, r = map(int ,input().split())
      start -= 1
      goal -= 1
      
      if r:
        edges = time_edges
      else:
        edges = cost_edges
  
      que = [(0, start)]
      visited = [False for _ in range(m)]
      
      while True:
        score, station = hpop(que)
        visited[station] = True
        
        if station == goal:
          print(score)
          break
  
        for c, to_station in edges[station]:
          if not visited[to_station]:
            hpush(que, (score + c, to_station))

main()

Submission status: Accepted

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] = C[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: Accepted

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 min > cost[i]:
				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: Accepted

Solution code:
from heapq import heappush, heappop
import sys
readline = sys.stdin.readline
write = sys.stdout.write
def solve():
    M, N = map(int, readline().split())
    if M == N == 0:
        return False
    G = [[] for i in range(N)]
    INF = 10**18
    def solve(s, t, u):
        dist = [INF]*N
        dist[s] = 0
        que = [(0, s)]
        while que:
            cost, v = heappop(que)
            if dist[v] < cost:
                continue
            for e in G[v]:
                w = e[0]
                if cost + e[u] < dist[w]:
                    dist[w] = d = cost + e[u]
                    heappush(que, (d, w))
        return dist[t]
    for i in range(M):
        a, b, c, t = map(int, readline().split()); a -= 1; b -= 1
        G[a].append((b, c, t))
        G[b].append((a, c, t))
    K = int(readline())
    for i in range(K):
        p, q, r = map(int, readline().split())
        write("%d\n" % solve(p-1, q-1, r+1))
    return True
while solve():
    ...

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

def Dijkstra(graph, start, goal):
    que = [(0, start)]
    visited = [False] * len(graph)
    while True:
        path_len, v = heappop(que)
        visited[v] = True
        if v == goal:
            print(path_len)
            break
        for w, edge_len in graph[v].items():
            if not visited[w]:
                heappush(que, (path_len + edge_len, w))

while(True):
    dicco = {}
    dicti = {}
    n,m = map(int, input().split())
    if n == 0 and m == 0:
        break
    for i in range(m):
        dicco[i] = {}
        dicti[i] = {}
    for _ in range(n):
        a,b,c,t = map(int, input().split())
        dicco[a-1][b-1] = c
        dicco[b-1][a-1] = c
        dicti[a-1][b-1] = t
        dicti[b-1][a-1] = t
    k = int(input())
    for _ in range(k):
        p,q,r = map(int, input().split())
        if not r:
            Dijkstra(dicco, p-1, q-1)
        else:
            Dijkstra(dicti, p-1, q-1)

Submission status: Accepted

Solution code:
def warshall_floyd(v_count: int, matrix: list) -> list:
    """ ワーシャルフロイド
    :param v_count: 頂点数
    :param matrix: 隣接行列(到達不能はfloat("inf"))
    """
    # 到達不能をfloat("inf")にしておけば余計なチェックを入れなくても
    # inf > inf+(-1) のような到達不能＋負辺が繋がってしまうことはない
    for i in range(v_count):
        for j, c2 in enumerate(row[i] for row in matrix):
            for k, (c1, c3) in enumerate(zip(matrix[j], matrix[i])):
                if c1 > c2+c3:
                    matrix[j][k] = c2+c3
    return matrix

while True:
    e_count, v_count = map(int, input().split())
    if not e_count:
        break
    inf = float("inf")
    edges_cost, edges_time = [[inf]*v_count for _ in [0]*v_count], [[inf]*v_count for _ in [0]*v_count]
    for _ in [0]*e_count:
        a, b, cost, time = map(int, input().split())
        a, b = a-1, b-1
        edges_cost[a][b] = cost
        edges_cost[b][a] = cost
        edges_time[a][b] = time
        edges_time[b][a] = time

    warshall_floyd(v_count, edges_cost)
    warshall_floyd(v_count, edges_time)

    for _ in [0]*int(input()):
        p, q, r = map(int, input().split())
        print((edges_time if r else edges_cost)[p-1][q-1])

Submission status: Runtime Error

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
	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()) # 駅 駅 time cost
		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: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
def MakeRouteList(ite,start,end):
    '''make all routes list from start to end station'''
    ite.sort()
    
    output = []
    # 1個め
    for k in range(len(ite)):
        # from start
        route = []
        if ite[k][0]==start:
            route = [ite[k]]
            output.append(route)
    # 2個め以降        
    for j in range(len(output)):
        for k in range(len(ite)):
            if output[j][-1][1] == ite[k][0]:
                output[j].append(ite[k])
    '''output = [[(1, 2, 200, 10), (2, 4, 100, 10), (4, 5, 150, 20)],
    [(1, 3, 250, 25), (3, 5, 300, 20)],[(1, 4, 400, 15), (4, 5, 150, 20)]]'''
    for k in range(len(output)):
        output[k].append(0)
        output[k].append(0)
    for j in range(len(output[k])-2):
        output[k][-2] += output[k][j][2] # cost
        output[k][-1] += output[k][j][3] # time
    """output = [[[1, 2, 200, 10], [2, 4, 100, 10], [4, 5, 150, 20], 450, 40],
 [[1, 3, 250, 25], [3, 5, 300, 20], 550, 45],
 [[1, 4, 400, 15], [4, 5, 150, 20], 550, 35]]
"""
    return output

def MinMoney(output):
    cost_temp = []
    for k in range(len(output)):
        cost_temp.append(output[k][-2])
    return min(cost_temp)
    
def MinTime(output):
    time_temp = []
    for k in range(len(output)):
        time_temp.append(output[k][-1])
    return min(time_temp)

while True:
    # n = senro_num; m = station_num
    n,m = map(int,raw_input().split())
    
    senro_list = []
    for j in range(n):
        senro = map(int,raw_input().split())
        senro_list.append(senro)
    
    # toiawase_num
    k = int(raw_input()) 
    toiawase_list=[]
    for jj in range(k):
        toiawase = map(int,raw_input().split())
        toiawase_list.append(toiawase)
    
    
    for p,q,r in toiawase_list:
        route = MakeRouteList(senro_list,p,q)
        if r == 0:
            print MinMoney(route)
        elif r == 1:
            print MinTime(route)            
    
    zero = map(int,raw_input().split())
    if zero == [0,0]:
        break

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
def MakeRouteList(ite,start,end):
    '''make all routes list from start to end station'''
    ite.sort()
    
    output = []
    # 1個め
    for k in range(len(ite)):
        # from start
        route = []
        if ite[k][0]==start:
            route = [ite[k]]
            output.append(route)
    # 2個め以降        
    for j in range(len(output)):
        for k in range(len(ite)):
            if output[j][-1][1] == ite[k][0]:
                output[j].append(ite[k])
    '''output = [[(1, 2, 200, 10), (2, 4, 100, 10), (4, 5, 150, 20)],
    [(1, 3, 250, 25), (3, 5, 300, 20)],[(1, 4, 400, 15), (4, 5, 150, 20)]]'''
    for k in range(len(output)):
        output[k].append(0)
        output[k].append(0)
    for j in range(len(output[k])-2):
        output[k][-2] += output[k][j][2] # cost
        output[k][-1] += output[k][j][3] # time
    """output = [[[1, 2, 200, 10], [2, 4, 100, 10], [4, 5, 150, 20], 450, 40],
 [[1, 3, 250, 25], [3, 5, 300, 20], 550, 45],
 [[1, 4, 400, 15], [4, 5, 150, 20], 550, 35]]
"""
    return output

def MinMoney(output):
    cost_temp = []
    for k in range(len(output)):
        cost_temp.append(output[k][-2])
    return min(cost_temp)
    
def MinTime(output):
    time_temp = []
    for k in range(len(output)):
        time_temp.append(output[k][-1])
    return min(time_temp)

while True:
    # n = senro_num; m = station_num
    try:
        n,m = map(int,raw_input().split())
    except EOFError:
        break
    senro_list = []
    for j in range(n):
        senro = map(int,raw_input().split())
        senro_list.append(senro)
    
    # toiawase_num
    k = int(raw_input()) 
    toiawase_list=[]
    for jj in range(k):
        toiawase = map(int,raw_input().split())
        toiawase_list.append(toiawase)
    
    
    for p,q,r in toiawase_list:
        route = MakeRouteList(senro_list,p,q)
        if r == 0:
            print MinMoney(route)
        elif r == 1:
            print MinTime(route)            
    
    zero = map(int,raw_input().split())
    if zero == [0,0]:
        break