Problem:


温泉旅行

温泉好きのたけしさんは、次の長期休暇を利用してとある温泉地への旅行を計画しています。移動は長距離バスを乗り継ぎ、なるべくお金をかけずに目的地へたどり着きたいと思っています。貯金があるとはいえ、資金に心許ないたけしさんは、おじいさんに相談することにしました。計画を聞いて感心したおじいさんは、たけしさんに特別な切符を渡しました。

その切符は、長距離バスの連続した2区間を1回だけ無料で乗れるというものでした。使いようによってはかなりの移動費削減が見込めますが、より大きな効果を発揮させるためにはしっかりした計画を練る必要があります。

出発地と目的地、及び中継地点が合わせて n 個、2つの地点を結ぶ路線が m 個与えられます。各地点にはそれぞれ 1 から n までの数字が割り振られています。出発地は 1、目的地は n です。路線の情報は、その路線が結ぶ2つの地点 a と b、及びその料金 c で表されます。特別な切符の効力により、任意の地点から、一度だけ連続した2つの路線を料金0で通過することができます。ただし、途中で目的地を通過しても、目的地にたどり着いたことにはなりません。

出発地、目的地、及び中継地点の総数 n と路線の数 m、各路線の情報を入力とし、料金の最小値を出力するプログラムを作成してください。ただし、必ず出発地から目的地へと到達する経路が存在するものとします。

入力

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

n m
a1 b1 c1
a2 b2 c2
:
am bm cm

1行目に出発地、目的地、及び中継地点の総数 n (2 ≤ n ≤ 100)と路線の数 m (1 ≤ m ≤ 300)が与えられます。続く m 行に各路線の情報 ai, bi,  ci (1 ≤ ci ≤ 1000) が与えられます。

データセットの数は 40 を超えません。

出力

入力データセットごとに、料金の最小値を1行に出力します。

入力例

2 1
1 2 5
3 2
1 2 5
2 3 5
6 9
1 2 7
1 3 9
1 5 14
2 3 10
2 4 15
3 4 11
3 5 2
4 5 9
4 6 8
0 0

出力例

5
0
7



Sample input:
2 1
1 2 5
3 2
1 2 5
2 3 5
6 9
1 2 7
1 3 9
1 5 14
2 3 10
2 4 15
3 4 11
3 5 2
4 5 9
4 6 8
0 0


Sample output:
5
0
7

Submission status: Wrong Answer

Solution code:
while 1:
    n,m = list(map(int,input().split()))
    if n == 0:break
    costs = {x:[] for x in range(1,n+1)}
    min_cost = [[-1 for x in range(3)] for y in range(n+1)]
    for i in range(m):
        a,b,c = list(map(int,input().split()))
        costs[a].append((b,c))
        costs[b].append((a,c))

    spam = [(0,1,2)] #(cost,num,free tickets count)
    while len(spam) > 0:
        mc = min(spam)
        spam.remove(mc)
        if min_cost[mc[1]][mc[2]] >= 0:
            continue

        min_cost[mc[1]][mc[2]] = mc[0]

        #移動できる場所の登録
        for cv in costs[mc[1]]:
            #チケット不使用
            if mc[2] == 2:
                spam.append((mc[0] + cv[1],cv[0],2))
            #チケット使用
            if mc[2] > 0:
                spam.append((mc[0],cv[0],mc[2]-1))

    print(min(min_cost[n]))

Submission status: Wrong Answer

Solution code:
MAX_VAL = 99999999999
while 1:
    n,m = list(map(int,input().split()))
    if n == 0:break
    costs = {x:[] for x in range(1,n+1)}
    min_cost = [[MAX_VAL for x in range(2)] for y in range(n+1)]
    for i in range(m):
        a,b,c = list(map(int,input().split()))
        costs[a].append((b,c))
        costs[b].append((a,c))

    spam = [(0,1,2)] #(cost,num,free tickets count)
    while len(spam) > 0:
        mc = min(spam)
        spam.remove(mc)

        tic_i = 0 if mc[2] == 2 else 1

        if mc[2] != 1 and min_cost[mc[1]][tic_i] != MAX_VAL:
            continue

        if mc[2] != 1:
            min_cost[mc[1]][tic_i] = mc[0]

        #移動できる場所の登録
        for cv in costs[mc[1]]:
            #チケット不使用
            if mc[2] != 1:
                spam.append((mc[0] + cv[1],cv[0],mc[2]))
            #チケット使用
            if mc[2] > 0:
                spam.append((mc[0],cv[0],mc[2]-1))

        print(spam)

    #print(min_cost[n])
    print(min(min_cost[n]))

Submission status: Wrong Answer

Solution code:
import copy

def f1(p, cost, route):
    for k, c in data.items():
        a, b = k
        if p == a:
            if not b in route:
                v1, v2, v3 = f2(p, c, cost)
                if not b in cost or v1 < cost[b][0]:
                    cost[b] = [v1, v2, v3]
        elif p == b:
            if not a in route:
                v1, v2, v3 = f2(p, c, cost)
                if not a in cost or v1 < cost[a][0]:
                    cost[a] = [v1, v2, v3]
    else:
        del cost[p]
    p, v = sorted(cost.items(), key=lambda x: x[0])[0]
    if p == g:
        return cost[g][0]
    else:
        route.append(p)
        return f1(p, cost, route)
        
def f2(p, c, cost):
    lis = copy.deepcopy(cost[p])
    if not cost[p][1]:
        lis[0] += c
        lis[1].append(c)
        lis[2] = c
    elif len(cost[p][1]) == 1:
        lis[0] = 0
        lis[1].append(c)
        lis[2] = c
    else:
        if sum(lis[1]) < lis[2]+c:
            lis[0] = lis[0]+sum(lis[1])-lis[2]
            lis[1] = [lis[2], c]
            lis[2] = c
        else:
            lis[0] += c
            lis[2] = c
    return lis

while True:
    g, n = map(int, raw_input().split())
    if g == n == 0: break
    data = {}
    for i in range(n):
        a, b, c = map(int, raw_input().split())
        data[(a, b)] = c
    print f1(1, cost={1:[0, [], 0]}, route=[1])

Submission status: Wrong Answer

Solution code:
import copy

def f1(p, cost, route):
    for k, c in data.items():
        a, b = k
        if p == a:
            if not b in route:
                v1, v2, v3 = f2(p, c, cost)
                if not b in cost or v1 < cost[b][0]:
                    cost[b] = [v1, v2, v3]
        elif p == b:
            if not a in route:
                v1, v2, v3 = f2(p, c, cost)
                if not a in cost or v1 < cost[a][0]:
                    cost[a] = [v1, v2, v3]
    else:
        del cost[p]
    p, v = sorted(cost.items(), key=lambda x: x[0])[0]
    if p == g:
        return cost[g][0]
    else:
        route.append(p)
        return f1(p, cost, route)
        
def f2(p, c, cost):
    lis = copy.deepcopy(cost[p])
    if not cost[p][1]:
        lis[0] += c
        lis[1].append(c)
        lis[2] = c
    elif len(cost[p][1]) == 1:
        lis[0] = 0
        lis[1].append(c)
        lis[2] = c
    else:
        if sum(lis[1]) < lis[2]+c:
            lis[0] = lis[0]+sum(lis[1])-lis[2]
            lis[1] = [lis[2], c]
            lis[2] = c
        else:
            lis[0] += c
            lis[2] = c
    return lis

while True:
    g, n = map(int, raw_input().split())
    if g == n == 0: break
    data = {}
    for i in range(n):
        a, b, c = map(int, raw_input().split())
        data[(a, b)] = c
    else:
        print f1(1, cost={1:[0, [], 0]}, route=[1])

Submission status: Wrong Answer

Solution code:
import copy

def f1(p, cost, route):
    for k, c in data.items():
        a, b = k
        if p == a:
            if not b in route:
                v1, v2, v3 = f2(p, c, cost)
                if not b in cost or v1 < cost[b][0]:
                    cost[b] = [v1, v2, v3]
        elif p == b:
            if not a in route:
                v1, v2, v3 = f2(p, c, cost)
                if not a in cost or v1 < cost[a][0]:
                    cost[a] = [v1, v2, v3]
    else:
        del cost[p]
    p, v = sorted(cost.items(), key=lambda x: x[1][0])[0]
    if p == g:
        print cost
        return cost[g][0]
    else:
        route.append(p)
        print cost
        return f1(p, cost, route)
        
def f2(p, c, cost):
    lis = copy.deepcopy(cost[p])
    if not cost[p][1]:
        lis[0] += c
        lis[1].append(c)
        lis[2] = c
    elif len(cost[p][1]) == 1:
        lis[0] = 0
        lis[1].append(c)
        lis[2] = c
    else:
        if sum(lis[1]) < lis[2]+c:
            lis[0] = lis[0]+sum(lis[1])-lis[2]
            lis[1] = [lis[2], c]
            lis[2] = c
        else:
            lis[0] += c
            lis[2] = c
    return lis

while True:
    g, n = map(int, raw_input().split())
    if g == n == 0: break
    data = {}
    for i in range(n):
        a, b, c = map(int, raw_input().split())
        data[(a, b)] = c
    else:
        print f1(1, cost={1:[0, [], 0]}, route=[1])

Submission status: Accepted

Solution code:
MAX_VAL = 99999999999
while 1:
    n,m = list(map(int,input().split()))
    if n == 0:break
    costs = {x:[] for x in range(1,n+1)}
    min_cost = [[MAX_VAL for x in range(2)] for y in range(n+1)]
    for i in range(m):
        a,b,c = list(map(int,input().split()))
        costs[a].append((b,c))
        costs[b].append((a,c))

    spam = [(0,1,2)] #(cost,num,free tickets count)
    while len(spam) > 0:
        mc = min(spam)
        spam.remove(mc)

        tic_i = 0 if mc[2] == 2 else 1

        if mc[2] != 1 and min_cost[mc[1]][tic_i] != MAX_VAL:
            continue

        if mc[2] != 1:
            min_cost[mc[1]][tic_i] = mc[0]

        #移動できる場所の登録
        for cv in costs[mc[1]]:
            #チケット不使用
            if mc[2] != 1:
                spam.append((mc[0] + cv[1],cv[0],mc[2]))
            #チケット使用
            if mc[2] > 0:
                spam.append((mc[0],cv[0],mc[2]-1))

    #print(min_cost[n])
    print(min(min_cost[n]))

Submission status: Accepted

Solution code:
MAX_V = 999999999999999999999
while 1:
    n,m = list(map(int,input().split()))
    if n == 0:break
    costs = {x:[] for x in range(1,n+1)}
    passed = [[0 for x in range(2)] for y in range(n+1)]
    result = [MAX_V,MAX_V]
    for i in range(m):
        a,b,c = list(map(int,input().split()))
        costs[a].append((b,c))
        costs[b].append((a,c))

    spam = [(0,1,2)] #(cost,num,free tickets count)
    while len(spam) > 0:
        mc = min(spam)
        spam.remove(mc)

        tic_i = 0 if mc[2] == 2 else 1

        if mc[2] != 1 and passed[mc[1]][tic_i] != 0:
            continue

        if mc[2] != 1:
            passed[mc[1]][tic_i] = 1
            if n == mc[1]:
                result[tic_i] = mc[0]

        if max(result) < MAX_V:break

        #移動できる場所の登録
        for cv in costs[mc[1]]:
            #チケット不使用
            if mc[2] != 1:
                spam.append((mc[0] + cv[1],cv[0],mc[2]))
            #チケット使用
            if mc[2] > 0:
                spam.append((mc[0],cv[0],mc[2]-1))

    print(min(result))

Submission status: Accepted

Solution code:
MAX_V = 999999999999999999999
while 1:
    n,m = list(map(int,input().split()))
    if n == 0:break
    costs = {x:[] for x in range(1,n+1)}
    passed = [[False for x in range(2)] for y in range(n+1)]
    result = [MAX_V,MAX_V]
    for i in range(m):
        a,b,c = list(map(int,input().split()))
        costs[a].append((b,c))
        costs[b].append((a,c))

    spam = [(0,1,2)] #(cost,num,free tickets count)
    while len(spam) > 0:
        mc = min(spam)
        spam.remove(mc)

        tic_i = 0 if mc[2] == 2 else 1

        if mc[2] != 1 and passed[mc[1]][tic_i] :
            continue

        if mc[2] != 1:
            passed[mc[1]][tic_i] = True
            if n == mc[1]:
                result[tic_i] = mc[0]

        if max(result) < MAX_V:break

        #移動できる場所の登録
        for cv in costs[mc[1]]:
            #チケット不使用
            if mc[2] != 1:
                spam.append((mc[0] + cv[1],cv[0],mc[2]))
            #チケット使用
            if mc[2] > 0:
                spam.append((mc[0],cv[0],mc[2]-1))

    print(min(result))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

INF = 10 ** 20
while True:
  n, m = map(int, input().split())
  if n == 0:
    break
  edges = [[] for _ in range(n * 2)]
  for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append((b, c))
    edges[a + n].append((b + n, c))
    edges[b].append((a, c))
    edges[b + n].append((a + n, c))
  
  for i in range(n):
    adds = []
    for to, _ in edges[i]:
      if to < n:
        for toto, _ in edges[to]:
          if toto < n and toto != i:
            adds.append((toto + n, 0))
    edges[i].extend(adds)
  edges[n - 1].append((2 * n - 1, 0))
  
  costs = [INF] * (2 * n)
  que = []
  heappush(que, (0, 0))
  while que:
    total, node = heappop(que)
    for to, cost in edges[node]:
      if costs[to] > total + cost:
        costs[to] = total + cost
        heappush(que, (total + cost, to))
  print(costs[2 * n - 1])

Submission status: Accepted

Solution code:
def solve():
    from sys import stdin
    f_i = stdin
    
    from heapq import heappush, heappop
    while True:
        n, m = map(int, f_i.readline().split())
        if n == 0:
            break
        
        adj = [[] for i in range(n)]
        for i in range(m):
            a, b, c = map(int, f_i.readline().split())
            a -= 1
            b -= 1
            adj[a].append((b, c))
            adj[b].append((a, c))
        
        # Dijkstra's algorithm
        fare = [[100000] * 3 for i in range(n)]
        fare[0][2] = 0
        hq = [(0, 0, 2)] # (fare, pos, remaining ticket)
        n -= 1
        while hq:
            f1, u, rt = heappop(hq)
            
            if rt != 1 and u == n:
                print(f1)
                break
            
            for v, f2 in adj[u]:
                if rt == 0:
                    f3 = f1 + f2
                    if f3 < fare[v][0]:
                        fare[v][0] = f3
                        heappush(hq, (f3, v, 0))
                elif rt == 1:
                    if f1 < fare[v][0]:
                        fare[v][0] = f1
                        heappush(hq, (f1, v, 0))
                else:
                    f3 = f1 + f2
                    if f3 < fare[v][2]: # not using ticket
                        fare[v][2] = f3
                        heappush(hq, (f3, v, 2))
                    if f1 < fare[v][1]: # using ticket
                        fare[v][1] = f1
                        heappush(hq, (f1, v, 1))

solve()