Problem:


 高速バス

A 君は高校の休みを利用して、高速バス(以下、「バス」 )で一人旅をする計画を立てています。まず、A 君は一番行ってみたい町を選んでそこを目的地にしました。次に出発地から目的地までバスを乗り継いでいくルートを決めなければなりません。乗り継ぎをするときは、バスを降りてから別のバスに乗り換えるので、それぞれのバスの乗車券が必要になります。

 A 君は親戚のおじさんからバスの割引券を何枚かもらいました。   この券を 1 枚使うと乗車券 1 枚を半額で購入できます。例えば、図 1 の出発地5から目的地1へ行く場合には、5→4→6→2→1と5→3→1の二つの経路が考えられます。割引券が 2 枚あるとすると、交通費を最も安くするには5→4→6→2→1の経路をたどった場合、4→6と6→2の路線に割引を利用し、合計料金は 4600円となります。一方、5→3→1の経路をたどった場合、5→3と3→1の路線に割引を利用し、合計料金は 3750 円となります。

 A 君は観光にお金を回したいので、交通費はできるだけ少なくしようと考えています。そこで A 君は、出発地から目的地までの最も安い交通費を求めるプログラムを作成することにしました。

図1

 割引券の枚数、バスがつなぐ町の数、バスの路線数、各バスの路線情報を入力とし、出発地から目的地までの最も安い交通費を出力するプログラムを作成してください。各バスは双方向に同一料金で運行しています。また、町の数を n とすると、町にはそれぞれ異なる 1 から n までの番号が振られています。出発地から目的地までの経路は必ず存在するものとします。

Input

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

c n m s d
a1 b1 f1
a2 b2 f2
:
am bm fm

1 行目に割引券の枚数 c (1 ≤ c ≤ 10)、バスがつなぐ町の数 n (2 ≤ n ≤ 100)、バスの路線数 m (1 ≤ m ≤ 500)、出発地の町番号 s と目的地の町番号 d (s &ne; d)  が与えられます。

続く m 行に第 i のバスの路線情報 ai, bi, fi (1 ≤ ai, bi ≤ n, 1000 ≤ fi ≤ 10000) が与えられます。ai, bi はバスの路線の始点と終点の町番号、fi はこの路線の料金を表す100 刻みの整数です。

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

Output

入力データセットごとに、最も安い交通費を１行に出力します。

Sample Input

1 3 3 1 3
1 3 2000
1 2 1000
2 3 1000
2 3 3 1 3
1 3 2300
1 2 1000
2 3 1200
2 6 6 5 1
1 2 1500
1 3 4500
2 6 2000
5 4 1000
6 4 2200
3 5 3000
0 0 0 0 0

Output for the Sample Input

1000
1100
3750



Sample input:
1 3 3 1 3
1 3 2000
1 2 1000
2 3 1000
2 3 3 1 3
1 3 2300
1 2 1000
2 3 1200
2 6 6 5 1
1 2 1500
1 3 4500
2 6 2000
5 4 1000
6 4 2200
3 5 3000
0 0 0 0 0


Sample output:
1000
1100
3750

Submission status: Accepted

Solution code:
def solve():
    from heapq import heappush, heappop
    from sys import stdin
    f_i = stdin
    
    while True:
        c, n, m, s, d = map(int, f_i.readline().split())
        if c == 0:
            break
        s -= 1
        d -= 1
        
        adj = [[] for i in range(n)]
        for i in range(m):
            a, b, f = map(int, f_i.readline().split())
            a -= 1
            b -= 1
            adj[a].append((b, f))
            adj[b].append((a, f))
        
        # Dijkstra's algorithm
        fare = [[1000000] * (c + 1) for i in range(n)]
        fare[s][c] = 0
        hq = [(0, s, c)]
        while hq:
            f1, u, rc = heappop(hq) # rc: number of remaining coupons
            
            if u == d:
                print(f1)
                break
            
            for v, f2 in adj[u]:
                f3 = f1 + f2
                if f3 < fare[v][rc]: # not using coupon
                    fare[v][rc] = f3
                    heappush(hq, (f3, v, rc))
                f4 = f1 + f2 // 2
                if rc and f4 < fare[v][rc-1]: # using coupon
                    fare[v][rc-1] = f4
                    heappush(hq, (f4, v, rc - 1))

solve()

Submission status: Runtime Error

Solution code:
def express_bus(coupon,city,route,start,end):
    fare = {}
    adjacent = []
    for i in range(route):
        s,t,cost = map(int,raw_input().split())
        fare[s,t] = cost
        fare[t,s] = cost
    for i in range(1,city+1):
        adjacent.append([])
        for j in fare:
            if i == j[0]:
                adjacent[i-1].append(j[1])
    route = search(end,[start],adjacent)

    minimum_fare = []
    for path in route:
        each_path = [([path[i-1],path[i]]) for i in range(1,len(path))]
        costs = [fare[s,t] for s,t in each_path]
        total_fare = sum(costs)
        with_coupon = []
        for i in range(coupon):
            half_fare = max(costs)/2
            with_coupon.append(half_fare)
            costs.remove(max(costs))
            if costs == []:
                break
        minimum_fare.append(sum(costs+with_coupon))
    return min(minimum_fare)

def search(goal,path,adjacent,route=[]):
    n = path[len(path)-1]
    if n == goal:
        r = path[:]
        route.append(r)
    else:
        for i in adjacent[n-1]:
            if i not in path:
                path.append(i)
                search(goal,path,adjacent)
                path.pop()
    return route

while True:
    coupon,city,route,start,end = map(int,raw_input().split(" "))
    if city == 0 and route == 0 and coupon == 0:
        break
    print express_bus(coupon,city,route,start,end)

Submission status: Runtime Error

Solution code:
import sys

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

def get_state(a, c, k):
  return (a-1) * (c+1) + k

while True:
  c,n,m,s,d = map(int, raw_input().split())
  if c == 0:
    break
  matrix = [[sys.maxint] * n*(c+1) for i in xrange(n*(c+1))]
  for i in xrange(m):
    a,b,f = map(int, raw_input().split())
    # no use ticket
    for i in xrange(c+1):
      matrix[get_state(a, c, i)][get_state(b, c, i)] = f
      matrix[get_state(b, c, i)][get_state(a, c, i)] = f
    # use ticket
    for i in xrange(c):
      matrix[get_state(a, c, i)][get_state(b, c, i+1)] = f/2
      matrix[get_state(b, c, i)][get_state(a, c, i+1)] = f/2
  costs = dijkstra(n*(c+1), get_state(s, c, 0), matrix)
  mincost = sys.maxint
  for i in xrange(c+1):
    mincost = min(mincost, costs[get_state(d, c, i)])
  print mincost

Submission status: Runtime Error

Solution code:
from heapq import *

    while True:
    #input c,n,m,s,d & creating G
    #G[to,cost]
    c,n,m,s,d=map(int,input().split())
    
    if c==n==m==s==d==0:
        break
    
    G=[[]]
    for i in range(n):
        G.append([])
    for i in range(m):
        a,b,f=map(int,input().split())
        G[a].append([b,f])
        G[b].append([a,f])

    #creating dp[]
    INF=1e8
    dp=[]
    for i in range(c+1):
        temp=[INF for j in range(n+1)]
        dp.append(temp)

    def dijkstra(s,c):
        que=[]
        dp[0][s]=0
        heappush(que,[dp[c][s],s])

        while len(que)!=0:
            p=heappop(que)
            v=p[1] #v is the current location
            if(dp[c][v]<p[0]):
                continue
            for i in range(len(G[v])):
                e=G[v][i]
                Min=dp[c][v]+e[1] if c==0 else min(dp[c-1][v]+e[1]/2,dp[c][v]+e[1])
                if(dp[c][e[0]]>Min):
                    dp[c][e[0]]=Min
                    heappush(que,[dp[c][e[0]],e[0]])

    for i in range(c+1):
        dijkstra(s,i)
    print(int(dp[c][d]))