Problem:


Problem D: Mr. Rito Post Office

Mr. リトー郵便局

-->

あなたは離島の郵便局に勤めるプログラマである．あなたの住んでいる地域は，複数の島々からなる．各島には一つ以上の港町がある．それらに加えて他の町や村があるかもしない．ある島から別の島に向かうためには船を使わなければならない．一つの島の中を回るには陸路が使えるが，海路を利用した方が速いこともある．

近年行われた郵便局の民営化をきっかけに，経費削減に向けて郵便配達員の人員整理が全国的に行われた．離島の郵便局もその例外ではなく，結果として郵便配達員は利藤さんただ一人となってしまった．その郵便局が集配を担当する地域は非常に広いため，一人で集配するのは大変な作業である．なので，どのようにすれば効率的に集配を行えるのか，利藤さんがあなたに助けを求めてきた．

あなたの仕事は，利藤さんがたどるべき町や村の集配順序が与えられたときに，最短巡回経路を求めるプログラムを書くことである．

利藤さんは，決して指定された順序以外で集配業務を行うことができない．しかし，ある町や村から別の町や村へ移動する際に，他の町や村を経由して移動することは許可されている．また，利藤さんは島々を巡るための一隻の船を持っている．

例えば，町A，町B，村Cという集配順序が与えられた場合，町Aから町Bへ向かう際にどの町や村を経由してもかまわない．このとき，村Cを経由しても構わないが，集配順序を守るためには，一度町Bに行って集配をおこなってから，改めて村Cを訪れて集配をおこなわなければならない．また，町Aから海路を用いて町Bに向かい，町Bから陸路を用いて村Cに向かった場合，船を町Bに置いたままになる．したがって，次に海路を使いたい場合は町Bに戻る必要がある．

一つの町や村において複数回集配をしなければならない場合もある．たとえば，町A，村B，町C，村Bという集配順序が与えられるかもしれない．このとき，町Aから村Bをたどらずに町Cに向かった場合は，町Cでいきなり集配をおこなうことはできない．最初の村Bでの集配が終わっていないからである．町Cで集配を済ませた後で村Bを訪れて集配しても，一回目の村Bの集配を終わらせたことにはならない．

利藤さんは，はじめに必ずある港町に船とともにいる．利藤さんはベテランであるため，移動時間以外の集配作業にかかる時間は無視してよい．また，最後の町または村での集配業務が完了するまでの時間だけが問題であり，船をもとの位置に戻して郵便局に帰るまでの時間は考慮しなくてよい．

Input

入力は複数のデータセットから構成される．各データセットの形式は次に示すとおりである．

N M

x1 y1 t1 sl1

x2 y2 t2 sl2

...

xM yM tM slM

R

z1 z2 ... zR

データセットの中の入力項目は，すべて非負の整数である．行中の入力項目の区切りは空白 1 個である．

最初の行は，陸路及び海路網の大きさを規定する．

N (2 ≤ N ≤ 200) は，町または村の数である． 
それぞれの町または村には，1 から N までの固有の番号を割り当てる． 
M (1 ≤ M ≤ 10000) は，陸路と海路の合計本数である．

2 行目から 1 + M 行目は，陸路または海路の記述である．
xi と yi (1 ≤ xi, yi ≤ N) は両端の町または村の番号を表す．
ti (1 ≤ ti ≤ 1000) はその陸路または海路の移動時間を表す．
sli は &lsquo;L&rsquo; または &lsquo;S&rsquo; のいずれかであり，Lは陸路を，Sは海路をそれぞれ表す．

ある2つの町や村を直接結ぶ陸路または海路が2本以上存在することがある． それぞれの陸路または海路は双方向であり，すなわちどちらの向きにも移動できる．

M + 2 行目の R (1 ≤ R ≤
1000)は，利藤さんが担当する集配先の数を表す． M + 3 行目には，集配先の町や村の番号 zi (1 ≤ zi ≤ N) が集配順に R 個並んでいる．

初期状態では利藤さんと船はともに港町 z1 に存在する． 初期状態から集配先の町や村へは，必ず何らかの方法で移動することができる．

入力の終わりは，空白で区切られた2つの0を含む1行で示される．

Output

入力の各データセットに対して，与えられた集配順序で利藤さんが町と村を巡回するために必要な最短移動時間を求め，1行に出力せよ．

Sample Input

3 3
1 2 5 L
1 2 7 S
2 3 11 S
3
1 2 3
5 5
1 2 15 L
2 3 10 L
4 5 7 L
1 3 30 S
3 4 100 S
5
1 3 5 4 1
0 0

Output for the Sample Input

18
269



Sample input:
3 3
1 2 5 L
1 2 7 S
2 3 11 S
3
1 2 3
5 5
1 2 15 L
2 3 10 L
4 5 7 L
1 3 30 S
3 4 100 S
5
1 3 5 4 1
0 0


Sample output:
18
269

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop

def main():
  while True:
    n, m = map(int, input().split())
    if n == 0:break
    land_route = [[] for _ in range(n)]
    sea_route = [[] for _ in range(n)]
    for _ in range(m):
      x, y, t, s = input().split()
      x, y, t = int(x) - 1, int(y) - 1, int(t)
      if s == "L":
        land_route[x].append((y, t))
        land_route[y].append((x, t))
      if s == "S":
        sea_route[x].append((y, t))
        sea_route[y].append((x, t))
    
    r = int(input())
    zlst = list(map(int, input().split()))
    zlst = [i - 1 for i in zlst]
    dic = {} #dic[(pos1, pos2, visited)]
    dic[(zlst[0], zlst[0], 0)] = 0
    que = []
    heappush(que, (0, 0, zlst[0], zlst[0]))
    while que:
      score, index, pos1, pos2 = heappop(que)
      if index == r - 1:
        print(score)
        break
    
      for to, cost in land_route[pos1]:
        new_score = score + cost
        if to == zlst[index + 1]:
          if (to, pos2, index + 1) not in dic or dic[(to, pos2, index + 1)] > new_score:
            dic[(to, pos2, index + 1)] = new_score
            heappush(que, (new_score, index + 1, to, pos2))
        else:
          if (to, pos2, index) not in dic or dic[(to, pos2, index)] > new_score:
            dic[(to, pos2, index)] = new_score
            heappush(que, (new_score, index, to, pos2))
    
      if pos1 != pos2:continue
    
      for to, cost in sea_route[pos1]:
        new_score = score + cost
        if to == zlst[index + 1]:
          if (to, to, index + 1) not in dic or dic[(to, to, index + 1)] > new_score:
            dic[(to, to, index + 1)] = new_score
            heappush(que, (new_score, index + 1, to, to))
        else:
          if (to, to, index) not in dic or dic[(to, to, index)] > new_score:
            dic[(to, to, index)] = new_score
            heappush(que, (new_score, index, to, to))
    
main()

Submission status: Memory Limit Exceeded

Solution code:
from queue import PriorityQueue
inf = 10**9
while True:
    n, m = map(int, input().split())
    if n == 0:
        break
    edgel = [[] for i in range(n)]
    edges = [[] for i in range(n)]
    for i in range(m):
        x, y, t, sl = input().split()
        x = int(x) - 1
        y = int(y) - 1
        t = int(t)
        if sl == 'L':
            edgel[x].append([y, t])
            edgel[y].append([x, t])
        else:
            edges[x].append([y, t])
            edges[y].append([x, t])
    r = int(input())
    z = list(map(int, input().split()))
    for i in range(r):
        z[i] -= 1
    dp = [[[inf] * n for i in range(n)] for j in range(r)]
    dp[0][z[0]][z[0]] = 0
    for i in range(1, r):
        pq = PriorityQueue()
        for j in range(n):
            if dp[i - 1][z[i - 1]][j] != inf:
                pq.put([dp[i - 1][z[i - 1]][j], z[i - 1], j])
                dp[i][z[i - 1]][j] = dp[i - 1][z[i - 1]][j]
        while not pq.empty():
            d, pos, f = pq.get()
            if d > dp[i][pos][f]:
                continue
            for j in range(len(edgel[pos])):
                to, add = edgel[pos][j]
                if dp[i][to][f] > dp[i][pos][f] + add:
                    dp[i][to][f] = dp[i][pos][f] + add
                    pq.put([dp[i][to][f], to, f])
            if pos == f:
                for j in range(len(edges[pos])):
                    to, add = edges[pos][j]
                    if dp[i][to][to] > dp[i][pos][f] + add:
                        dp[i][to][to] = dp[i][pos][f] + add
                        pq.put([dp[i][to][to], to, to])
    ret = inf
    for i in range(n):
        ret = min(ret, dp[r - 1][z[r - 1]][i])
    print(ret)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import sys, operator
INF = 10**18
def solve():
    readline = sys.stdin.readline
    write = sys.stdout.write
    N, M = map(int, readline().split())
    if N == M == 0:
        return False
    def dijkstra(N, s, G):
        dist = [INF]*N
        dist[s] = 0
        que = [(0, s)]
        while que:
            cost, v = heappop(que)
            if dist[v] < cost:
                continue
            for w, d in G[v]:
                if cost + d < dist[w]:
                    dist[w] = r = cost + d
                    heappush(que, (r, w))
        return dist
    rN = range(N)
    GL = [[] for i in rN]
    GS = [[] for i in rN]
    for i in range(M):
        x, y, t, sl = readline().split()
        x = int(x)-1; y = int(y)-1; t = int(t)
        if sl == 'L':
            GL[x].append((y, t))
            GL[y].append((x, t))
        else:
            GS[x].append((y, t))
            GS[y].append((x, t))
    EL = [dijkstra(N, i, GL) for i in rN]
    ES = [dijkstra(N, i, GS) for i in rN]

    R = int(readline())
    *Z, = map(int, readline().split())
    iv = [INF]*N
    S = [INF]*N; T = [0]*N
    D = [0]*N
    prv = Z[0]-1
    S[prv] = 0
    oadd = operator.add
    for z in Z[1:]:
        z -= 1
        A = EL[prv]; B = EL[z]
        v = A[z]
        D[:] = map(oadd, S, A)
        for j in rN:
            C = ES[j]
            b = B[j]
            T[j] = min(S[j] + v, min(map(oadd, D, C)) + b)
        S, T = T, S
        prv = z
    write("%d\n" % min(S))
    return True
while solve():
    ...

Submission status: Accepted

Solution code:
# # AOJ 2200
#
# INF = float('inf')
#
#
# def floyd_warshall(d):
#     v = len(d)
#     for k in range(v):
#         dk = d[k]
#         for i in range(v):
#             di = d[i]
#             for j in range(v):
#                 di[j] = min(di[j], di[k] + dk[j])
#
#
# def main():
#     while True:
#         N, M = map(int, input().split())
#         if N == M == 0:
#             break
#
#         sea = [[INF] * N for i in range(N)]
#         land = [[INF] * N for i in range(N)]
#         for i in range(N):
#             sea[i][i] = land[i][i] = 0
#
#         for i in range(M):
#             x, y, t, sl = input().split()
#             x = int(x) - 1
#             y = int(y) - 1
#             t = int(t)
#             if sl == 'S':
#                 sea[x][y] = sea[y][x] = min(sea[x][y], t)
#             else:
#                 land[x][y] = land[y][x] = min(land[x][y], t)
#
#         R = int(input())
#         z = list(map(lambda x: int(x) - 1, input().split()))
#
#         floyd_warshall(sea)
#         floyd_warshall(land)
#
#         dp = [INF] * N
#         dp[z[0]] = 0
#         for k in range(1, R):
#             ndp = [INF] * N
#             z1 = z[k-1]
#             z2 = z[k]
#             land_z1 = land[z1]
#             land_z2 = land[z2]
#             land_z1_z2 = land_z1[z2]
#
#             for i in range(N):
#                 tmp = dp[i] + land_z1_z2
#                 land_i_z2 = land_z2[i]
#                 sea_i = sea[i]
#
#                 for j in range(N):
#                     # ship originally at j
#                     # z1 -> (land) -> j -> (sea) -> i -> (land) -> z2
#                     tmp = min(tmp, dp[j] + land_z1[j] + sea_i[j] + land_i_z2)
#
#                 ndp[i] = tmp
#             dp = ndp
#         print(min(dp))
#
#
# if __name__ == '__main__':
#     main()

inf = float("INF")

class Warshall_Floyd:

    def __init__(self, n, dist):
        self.dist = dist
        self.n = n

    def search(self):
        n = self.n
        dist = self.dist
        for i in range(n):
            dist[i][i] = 0

        for i in range(n):
            di = dist[i]
            for j in range(n):
                dj = dist[j]
                if i == j:
                    continue
                for k in range(n):
                    if dj[k] > dj[i] + di[k]:
                        dj[k] = dj[i] + di[k]

        return dist

import sys


def main(n, m):
    dps = [[inf] * n for i in range(n)]
    dpl = [[inf] * n for i in range(n)]

    for _ in range(m):
        x, y, t, sl = input().split()
        x, y, t = map(lambda x: int(x) - 1, [x, y, t])
        t += 1
        if sl == "S":
            dps[x][y] = t
            dps[y][x] = t
        if sl == "L":
            dpl[x][y] = t
            dpl[y][x] = t

    l = Warshall_Floyd(n, dpl)
    s = Warshall_Floyd(n, dps)
    dpl = l.search()
    dps = s.search()

    r = int(input())
    v = list(map(lambda x: int(x) - 1, input().split()))
    dp1 = [inf] * n
    dp1[v[0]] = 0

    for i in range(r-1):
        b = v[i]
        c = v[i + 1]
        dp2 = [0] * n
        dplb = dpl[b]
        dpk = [dp1[k] + dplb[k] for k in range(n)]

        for j in range(n):
            # 陸路のみ
            # 船の位置は変わらず
            dp2[j] = dp1[j] + dplb[c]

            dpljc = dpl[j][c]
            dpsj = dps[j]
            tmp = dp2[j]

            for k in range(n):
                # 海路あり
                # kに船があるとき
                # v[i-1]→(陸路)→k→(海路)→j→(陸路)→v[i]
                # この時船はjに保管される
                tmp1 = dpk[k] + dpsj[k] + dpljc
                if tmp > tmp1:
                    tmp = tmp1

            dp2[j] = tmp

        dp1 = dp2

    print(min(dp1))


while 1:
    n, m = map(int, input().split())
    if n == m == 0:
        break
    main(n, m)

Submission status: Accepted

Solution code:
inf = float("INF")

class Warshall_Floyd:

    def __init__(self, n, dist):
        self.dist = dist
        self.n = n

    def search(self):
        n = self.n
        dist = self.dist
        for i in range(n):
            dist[i][i] = 0

        for i in range(n):
            di = dist[i]
            for j in range(n):
                dj = dist[j]
                if i == j:
                    continue
                for k in range(n):
                    if dj[k] > dj[i] + di[k]:
                        dj[k] = dj[i] + di[k]

        return dist

import sys


def m():
    def main(n, m):
        dps = [[inf] * n for i in range(n)]
        dpl = [[inf] * n for i in range(n)]

        for _ in range(m):
            x, y, t, sl = sys.stdin.readline().split()
            x, y, t = map(lambda x: int(x) - 1, [x, y, t])
            t += 1
            if sl == "S":
                dps[x][y] = t
                dps[y][x] = t
            if sl == "L":
                dpl[x][y] = t
                dpl[y][x] = t

        l = Warshall_Floyd(n, dpl)
        s = Warshall_Floyd(n, dps)
        dpl = l.search()
        dps = s.search()

        r = int(input())
        v = list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))
        dp1 = [inf] * n
        dp1[v[0]] = 0

        for i in range(r-1):
            b = v[i]
            c = v[i + 1]
            dp2 = [0] * n
            dplb = dpl[b]
            dpk = [dp1[k] + dplb[k] for k in range(n)]

            for j in range(n):
                # 陸路のみ
                # 船の位置は変わらず 
                dp2[j] = dp1[j] + dplb[c]

                dpljc = dpl[j][c]
                dpsj = dps[j]
                tmp = dp2[j]

                for k in range(n):
                    # 海路あり
                    # kに船があるとき
                    # v[i-1]→(陸路)→k→(海路)→j→(陸路)→v[i]
                    # この時船はjに保管される
                    tmp1 = dpk[k] + dpsj[k] + dpljc
                    if tmp > tmp1:
                        tmp = tmp1

                dp2[j] = tmp

            dp1 = dp2

        print(min(dp1))

    while 1:
        n, m = map(int, input().split())
        if n == m == 0:
            break
        main(n, m)
if __name__ == "__main__":
    m()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

class WarshallFloyd():
    def __init__(self, e, n):
        self.E = e
        self.N = n

    def search(self):
        n = self.N
        nl = list(range(n))
        d = [[inf] * n for _ in nl]
        for i in range(n):
            d[i][i] = 0
        for k,v in self.E.items():
            dk = d[k]
            for b,c in v:
                # consider multiple edges
                if dk[b] > c:
                    dk[b] = c
        for i in nl:
            di = d[i]
            for j in nl:
                if i == j:
                    continue
                dj = d[j]
                for k in nl:
                    if i != k and j != k and dj[k] > dj[i] + di[k]:
                        dj[k] = dj[i] + di[k]
        return d


def main():
    rr = []

    def f(n,m):
        le = collections.defaultdict(list)
        se = collections.defaultdict(list)
        for _ in range(m):
            l = LS()
            a,b,t = map(int, l[:-1])
            a -= 1
            b -= 1
            if l[-1] == 'S':
                se[a].append((b,t))
                se[b].append((a,t))
            else:
                le[a].append((b,t))
                le[b].append((a,t))
        q = I()
        qa = LI_()
        lw = WarshallFloyd(le, n)
        sw = WarshallFloyd(se, n)
        ld = lw.search()
        sd = sw.search()
        dp = [inf] * n
        dp[qa[0]] = 0
        # print('ld')
        # print('\n'.join('\t'.join(map(lambda x: '-' if x == inf else str(x), c)) for c in ld))
        # print('sd')
        # print('\n'.join('\t'.join(map(lambda x: '-' if x == inf else str(x), c)) for c in sd))
        for i in range(q-1):
            c = qa[i]
            ne = qa[i+1]
            lp = [inf] * n
            np = [inf] * n
            for j in range(n):
                np[j] = dp[j] + ld[c][ne]
                dj = dp[j] + ld[c][j]
                sdj = sd[j]
                for k in range(n):
                    if lp[k] > dj + sdj[k]:
                        lp[k] = dj + sdj[k]
            for j in range(n):
                if np[j] > lp[j] + ld[j][ne]:
                    np[j] = lp[j] + ld[j][ne]
            # print('cne', c, ne)
            # print('dp', dp)
            # print('lp', lp)
            dp = np

        # print('edp', dp)
        return min(dp)

    while 1:
        n,m = LI()
        if n == 0 and m == 0:
            break
        rr.append(f(n,m))
        # print('rr', rr[-1])

    return '\n'.join(map(str,rr))


print(main())

Submission status: Runtime Error

Solution code:
while(1):
    [N,M]=[int(x) for x in raw_input().split()]
    if N==0:
        break
    else:
        landr=[[99999999 for x in range(N+1)] for y in range(N+1)]
        sear=[[99999999 for x in range(N+1)] for y in range(N+1)]
        islandname1=[i for i in range(N+1)] #ex.[0,0,2,3,3]
        islandname2=[[i] for i in range(N+1)] #ex.[[0,1],[],[2],[3,4],[]]
        for i in range(1,N+1):
            landr[i][i]=0
            sear[i][i]=0
        for i in range(M):
            dd=raw_input().split()
            [a,b]=sorted([int(x) for x in dd[:2]])
            d=int(dd[2])
            t=dd[3]
            if t=='S':
                if sear[a][b]>d:
                    sear[a][b]=d
                    sear[b][a]=d
            else:
                if landr[a][b]>d:
                    landr[a][b]=d
                    landr[b][a]=d
                #check if same island
                if islandname1[a]!=islandname1[b]: #a<b
                    islandnameold=islandname1[b]
                    for port in islandname2[islandname1[b]]:
                        islandname1[port]=islandname1[a]
                    islandname2[islandname1[a]].extend(islandname2[islandnameold])
        #floyd algorhythm
        for k in range(1,N+1):
            for i in range(1,N+1):
               for j in range(i,N+1):
                   if landr[i][j]>landr[i][k]+landr[k][j]:
                       landr[i][j]=landr[i][k]+landr[k][j]
                       landr[j][i]=landr[i][k]+landr[k][j]
                   if sear[i][j]>sear[i][k]+sear[k][j]:
                       sear[i][j]=sear[i][k]+sear[k][j]
                       sear[j][i]=sear[i][k]+sear[k][j]
        R=int(raw_input())
        dest=[int(x) for x in raw_input().split()]
        loc=dest[0]
        portold=[[dest[0],0]]
        for i in range(R-1):
            portnew=[]
            newloc=dest[i+1]
            newport_temp=islandname2[islandname1[newloc]]
            for np in newport_temp:
                mintime=999999999
                for opc in portold:
                    op=opc[0]
                    opt=opc[1]
                    mintime=min(mintime,opt+landr[loc][op]+sear[op][np]+landr[np][newloc])
                portnew.append([np,mintime])
            portold=portnew
            loc=dest[i+1]
            i=i+1
        ans=sorted(portold,key=lambda x:x[1])
        print ans[0][1]

Submission status: Runtime Error

Solution code:
while(1):
    [N,M]=[int(x) for x in raw_input().split()]
    if N==0:
        break
    else:
        landr=[[99999999 for x in range(N+1)] for y in range(N+1)]
        sear=[[99999999 for x in range(N+1)] for y in range(N+1)]
        islandname1=[i for i in range(N+1)] #ex.[0,0,2,3,3]
        islandname2=[[i] for i in range(N+1)] #ex.[[0,1],[],[2],[3,4],[]]
        for i in range(1,N+1):
            landr[i][i]=0
            sear[i][i]=0
        for i in range(M):
            dd=raw_input().split()
            [a,b]=sorted([int(x) for x in dd[:2]])
            d=int(dd[2])
            t=dd[3]
            if t=='S':
                if sear[a][b]>d:
                    sear[a][b]=d
                    sear[b][a]=d
            else:
                if landr[a][b]>d:
                    landr[a][b]=d
                    landr[b][a]=d
                #check if same island
                if islandname1[a]!=islandname1[b]: #a<b
                    islandnameold=islandname1[b]
                    for port in islandname2[islandname1[b]]:
                        islandname1[port]=islandname1[a]
                    islandname2[islandname1[a]].extend(islandname2[islandnameold])
        #floyd algorhythm
        for k in range(1,N+1):
            for i in range(1,N+1):
               for j in range(i,N+1):
                   if landr[i][j]>landr[i][k]+landr[k][j]:
                       landr[i][j]=landr[i][k]+landr[k][j]
                       landr[j][i]=landr[i][k]+landr[k][j]
                   if sear[i][j]>sear[i][k]+sear[k][j]:
                       sear[i][j]=sear[i][k]+sear[k][j]
                       sear[j][i]=sear[i][k]+sear[k][j]
        R=int(raw_input())
        dest=[int(x) for x in raw_input().split()]
        loc=dest[0]
        portold=[[dest[0],0]]
        for i in range(R-1):
            portnew=[]
            newloc=dest[i+1]
            newport_temp=islandname2[islandname1[newloc]]
            for np in newport_temp:
                mintime=999999999
                for opc in portold:
                    op=opc[0]
                    opt=opc[1]
                    mintime=min(mintime,opt+landr[loc][op]+sear[op][np]+landr[np][newloc])
                    if op==np:
                        mintime=min(mintime,opt+landr[loc][newloc])
                portnew.append([np,mintime])
            portold=portnew
            loc=dest[i+1]
            i=i+1
        ans=sorted(portold,key=lambda x:x[1])
        print ans[0][1]

Submission status: Runtime Error

Solution code:
from queue import PriorityQueue
inf = 10**9
while True:
    n, m = map(int, input().split())
    if n == 0:
        break
    edgel = [[] for i in range(n)]
    edges = [[] for i in range(n)]
    for i in range(m):
        x, y, t, sl = input().split()
        x = int(x) - 1
        y = int(y) - 1
        t = int(t)
        if sl == 'L':
            edgel[x].append([y, t])
            edgel[y].append([x, t])
        else:
            edges[x].append([y, t])
            edges[y].append([x, t])
    r = int(input())
    z = list(map(int, input().split()))
    for i in range(r):
        z[i] -= 1
    dp = [[[inf] * n for i in range(n)] for j in range(r)]
    dp[0][z[0]][z[0]] = 0
    for i in range(1, r):
        pq = PriorityQueue()
        for j in range(n):
            if dp[i - 1][z[i - 1]][j] != inf:
                pq.put([-dp[i - 1][z[i - 1]][j], z[i - 1], j])
                dp[i][z[i - 1]][j] = dp[i - 1][z[i - 1]][j]
        while not pq.empty():
            d, pos, f = pq.get()
            d *= -1
            if d > dp[i][pos][f]:
                continue
            for j in range(len(edgel[pos])):
                to, add = edgel[pos][j]
                if dp[i][to][f] > dp[i][pos][f] + add:
                    dp[i][to][f] = dp[i][pos][f] + add
                    pq.put([-dp[i][to][f], to, f])
            if pos == f:
                for j in range(len(edges[pos])):
                    to, add = edges[pos][j]
                    if dp[i][to][to] > dp[i][pos][f] + add:
                        dp[i][to][to] = dp[i][pos][f] + add
                        pq.put([-dp[i][to][to], to, to])
    ret = inf
    for i in range(n):
        ret = min(ret, dp[r - 1][z[r - 1]][i])
    print(ret)

Submission status: Runtime Error

Solution code:
inf = 10**9
dp = [[inf] * 200 for i in range(200)]
ldist = [[inf] * 200 for i in range(200)]
sdist = [[inf] * 200 for i in range(200)]
while True:
    n, m = map(int, input().split())
    if n == 0:
        break
    for i in range(n):
        for j in range(n):
            if i == j:
                ldist[i][j] = sdist[i][j] = 0
            else:
                ldist[i][j] = sdist[i][j] = inf
    for i in range(m):
        x, y, t, sl = input().split()
        x = int(x) - 1
        y = int(y) - 1
        t = int(t)
        if sl == 'L':
            ldist[x][y] = ldist[y][x] = min(ldist[x][y], t)
        elif sl == 'S':
            sdist[x][y] = sdist[y][x] = min(sdist[x][y], t)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                ldist[i][j] = min(ldist[i][j], ldist[i][k] + ldist[k][j])
                sdist[i][j] = min(sdist[i][j], sdist[i][k] + sdist[k][j])
    for i in range(n):
        for j in range(n):
            dp[i][j] = 0 if i == j else inf
    for i in range(n):
        for j in range(n):
            if i != j:
                dp[i][j] = min(dp[i][j], dp[j][j] + ldist[j][i])
    r = int(input())
    z = list(map(int, input().split()))
    for i in range(n):
        z[i] -= 1
    for i in range(n):
        if i != z[0]:
            for j in range(n):
                dp[i][j] = inf
    for i in range(1, r):
        for j in range(n):
            for k in range(n):
                if j != z[i - 1]:
                    dp[j][k] = min(dp[j][k], dp[z[i - 1]]
                                   [k] + ldist[z[i - 1]][j])
        for j in range(n):
            for k in range(n):
                dp[k][k] = min(dp[k][k], dp[j][j] + sdist[j][k])
        for j in range(n):
            for k in range(n):
                if j != k:
                    dp[j][k] = min(dp[j][k], dp[k][k] + ldist[k][j])
        for j in range(n):
            if j != z[i]:
                for k in range(n):
                    dp[j][k] = inf
    ret = inf
    for i in range(n):
        ret = min(ret, dp[z[r - 1]][i])
    print(ret)

Submission status: Runtime Error

Solution code:
inf = 10**9
dp = [[inf] * 200 for i in range(200)]
ldist = [[inf] * 200 for i in range(200)]
sdist = [[inf] * 200 for i in range(200)]
while True:
    n, m = map(int, input().split())
    if n == 0:
        break
    for i in range(n):
        for j in range(n):
            if i == j:
                ldist[i][j] = sdist[i][j] = 0
            else:
                ldist[i][j] = sdist[i][j] = inf
    for i in range(m):
        x, y, t, sl = input().split()
        x = int(x) - 1
        y = int(y) - 1
        t = int(t)
        if sl == 'L':
            ldist[x][y] = ldist[y][x] = min(ldist[x][y], t)
        elif sl == 'S':
            sdist[x][y] = sdist[y][x] = min(sdist[x][y], t)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                ldist[i][j] = min(ldist[i][j], ldist[i][k] + ldist[k][j])
                sdist[i][j] = min(sdist[i][j], sdist[i][k] + sdist[k][j])
    for i in range(n):
        for j in range(n):
            dp[i][j] = 0 if i == j else inf
    for i in range(n):
        for j in range(n):
            if i != j:
                dp[i][j] = min(dp[i][j], dp[j][j] + ldist[j][i])
    r = int(input())
    z = list(map(int, input().split()))
    for i in range(n):
        z[i] -= 1
    for i in range(n):
        if i != z[0]:
            for j in range(n):
                dp[i][j] = inf
    for i in range(1, r):
        for j in range(n):
            for k in range(n):
                if j != z[i - 1]:
                    dp[j][k] = min(dp[j][k], dp[z[i - 1]][k] + ldist[z[i - 1]][j])
        for j in range(n):
            for k in range(n):
                dp[k][k] = min(dp[k][k], dp[j][j] + sdist[j][k])
        for j in range(n):
            for k in range(n):
                if j != k:
                    dp[j][k] = min(dp[j][k], dp[k][k] + ldist[k][j])
        for j in range(n):
            if j != z[i]:
                for k in range(n):
                    dp[j][k] = inf
    ret = inf
    for i in range(n):
        ret = min(ret, dp[z[r - 1]][i])
    print(ret)

Submission status: Runtime Error

Solution code:
inf = 10**9
dp = [[inf] * 210 for i in range(210)]
ldist = [[inf] * 210 for i in range(210)]
sdist = [[inf] * 210 for i in range(210)]
while True:
    n, m = map(int, input().split())
    if n == 0:
        break
    for i in range(n):
        for j in range(n):
            if i == j:
                ldist[i][j] = sdist[i][j] = 0
            else:
                ldist[i][j] = sdist[i][j] = inf
    for i in range(m):
        x, y, t, sl = input().split()
        x = int(x) - 1
        y = int(y) - 1
        t = int(t)
        if sl == 'L':
            ldist[x][y] = ldist[y][x] = min(ldist[x][y], t)
        elif sl == 'S':
            sdist[x][y] = sdist[y][x] = min(sdist[x][y], t)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                ldist[i][j] = min(ldist[i][j], ldist[i][k] + ldist[k][j])
                sdist[i][j] = min(sdist[i][j], sdist[i][k] + sdist[k][j])
    for i in range(n):
        for j in range(n):
            dp[i][j] = 0 if i == j else inf
    for i in range(n):
        for j in range(n):
            if i != j:
                dp[i][j] = min(dp[i][j], dp[j][j] + ldist[j][i])
    r = int(input())
    z = list(map(int, input().split()))
    for i in range(n):
        z[i] -= 1
    for i in range(n):
        if i != z[0]:
            for j in range(n):
                dp[i][j] = inf
    for i in range(1, r):
        for j in range(n):
            for k in range(n):
                if j != z[i - 1]:
                    dp[j][k] = min(dp[j][k], dp[z[i - 1]]
                                   [k] + ldist[z[i - 1]][j])
        for j in range(n):
            for k in range(n):
                dp[k][k] = min(dp[k][k], dp[j][j] + sdist[j][k])
        for j in range(n):
            for k in range(n):
                if j != k:
                    dp[j][k] = min(dp[j][k], dp[k][k] + ldist[k][j])
        for j in range(n):
            if j != z[i]:
                for k in range(n):
                    dp[j][k] = inf
    ret = inf
    for i in range(n):
        ret = min(ret, dp[z[r - 1]][i])
    print(ret)