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: Wrong Answer

Solution code:
from sys import stdin
from heapq import heappush,heappop

while(True):
    c,n,m,s,d = map(int, stdin.readline().split())
    if not c: break
    ma = [[] for _ in range(n)]
    s -= 1
    d -= 1
    for _ in range(m):
        a,b,f = map(int, stdin.readline().split())
        a -= 1
        b -= 1
        ma[a].append([f,b])
        ma[b].append([f,a])
    cost = [[10**10]*(c+1) for _ in range(n)]
    cost[s][c] = 0
    que = [[ cost[s][c], s, c ]]
    while que:
        co, pl, ti = heappop(que)
        for fee, town in ma[pl]:
            if cost[town][ti] > co + fee:
                cost[town][ti] = co+fee
                heappush(que,[cost[town][ti],town,ti])
            if ti and cost[town][ti-1] > co+fee:
                cost[town][ti-1] = co + fee//2
                heappush(que,[cost[town][ti-1],town,ti-1])
    print(min(ma[d])[0])

Submission status: Wrong Answer

Solution code:
from sys import stdin
from heapq import heappush,heappop

while(True):
    c,n,m,s,d = map(int, stdin.readline().split())
    if not c: break
    ma = [[] for _ in range(n)]
    s -= 1
    d -= 1
    for _ in range(m):
        a,b,f = map(int, stdin.readline().split())
        a -= 1
        b -= 1
        ma[a].append([f,b])
        ma[b].append([f,a])
    cost = [[10**10]*(c+1) for _ in range(n)]
    cost[s][c] = 0
    que = [[ cost[s][c], s, c ]]
    while que:
        co, pl, ti = heappop(que)
        for fee, town in ma[pl]:
            if cost[town][ti] > co+fee:
                cost[town][ti] = co+fee
                heappush(que,[cost[town][ti],town,ti])
            if ti and cost[town][ti-1] > co+fee//2:
                cost[town][ti-1] = co+fee//2
                heappush(que,[cost[town][ti-1],town,ti-1])
    print(cost[d][0])

Submission status: Wrong Answer

Solution code:

while True:
    c,n,m,s,d = list(map(int,input().split()))

    if c==0 and n == 0 and m == 0 and s == 0 and d == 0 : break

    f_list = [[ 0 for i in range(n+1)] for j in range(n+1)]
    path = {}
    for i in range(m):
        a,b,f = (list(map(int,input().split())))

        def add_path(a,b,f):
            global path
            global f_list
            if not a in path:
                path[a] = [b]
            else:
                path[a].append(b)
            f_list[a][b] = f

        add_path(a,b,f)
        add_path(b,a,f)

    #keiro tansaku
    stack = []
    stack.append(path[s])
    min_path  = None
    min_val = 999999999999

    work_val = []
    work_path = []
    def path_val(path):
        global c
        path.sort()
        v = 0
        if len(path) < c:
            v = sum(path) / 2
        else:
            v = sum(path[-c:])/2
            v += sum(path[:-c])

        return v
        
    work_path.append(s)
    work_val.append(0)

    while len(stack) > 0:


        ham = stack[-1]
        if len(ham) == 0:
            # 1階層上に
            stack.pop()
            work_val.pop()
            work_path.pop()
            continue

        next_p = ham.pop()

        if next_p in work_path: #already passed
            continue

        work_val.append(f_list[work_path[-1]][next_p])
        work_path.append(next_p)

        if next_p == d: #goal
            spam_val = path_val(work_val)
            if min(spam_val,min_val) != min_val:
                min_val = spam_val
            work_val.pop()
            work_path.pop()

        else:
            stack.append(path[next_p])

    print(int(min_val))

Submission status: Wrong Answer

Solution code:
import sys

def dijkstra(nodes, start, goal, matrix):
  defnode = [False] * (nodes)
  cost = [sys.maxint] * (nodes)
  cost[start] = 0
  node = start
  while True:
    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]
    if minnode == goal:
      return cost[goal]
    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 range(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 range(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
  print dijkstra(n*(c+1), get_state(s, c, 0), get_state(d, c, c), matrix)

Submission status: Wrong Answer

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 or node == sys.maxint:
      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: Wrong Answer

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 or node == sys.maxint:
      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==n==m==s==d==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: Wrong Answer

Solution code:
""" Created by Jieyi on 10/31/16. """
import io
import sys
import heapq

# Simulate the redirect stdin.
from collections import defaultdict

if len(sys.argv) > 1:
    filename = sys.argv[1]
    inp = ''.join(open(filename, "r").readlines())
    sys.stdin = io.StringIO(inp)


def input_data():
    while True:
        tickets, vertices, edges, start, end = map(int, input().split())
        if 0 == tickets + vertices + edges + start + end:
            break

        # shortest_path = [[sys.maxsize for _ in range(vertices)] for _ in range(tickets)]
        shortest_path = [sys.maxsize for _ in range(vertices)]
        g = defaultdict(list)
        h = []
        # Generate a map.
        for _ in range(edges):
            i, j, fare = map(int, input().split())
            g[i].append((j, fare))
            g[j].append((i, fare))
        # (price, vertices, remainder ticket)
        heapq.heappush(h, (0, start, tickets))

        while True:
            if 0 == len(h):
                break
            head = heapq.heappop(h)
            for v, price in g[head[1]]:
                if shortest_path[v - 1] > head[0] + price:
                    shortest_path[v - 1] = min(shortest_path[v - 1], head[0] + price)
                    heapq.heappush(h, (shortest_path[v - 1], v, head[2]))
                if 0 != head[2]:
                    if shortest_path[v - 1] > head[0] + int(price / 2):
                        shortest_path[v - 1] = min(shortest_path[v - 1], head[0] + int(price / 2))
                        heapq.heappush(h, (shortest_path[v - 1], v, head[2] - 1))

        print(shortest_path[end - 1])


def main():
    input_data()


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
""" Created by Jieyi on 10/31/16. """
import io
import sys
import heapq

# Simulate the redirect stdin.
from collections import defaultdict

if len(sys.argv) > 1:
    filename = sys.argv[1]
    inp = ''.join(open(filename, "r").readlines())
    sys.stdin = io.StringIO(inp)


def input_data():
    while True:
        tickets, vertices, edges, start, end = map(int, input().split())
        if 0 == tickets + vertices + edges + start + end:
            break

        shortest_path = [[sys.maxsize for _ in range(vertices)] for _ in range(tickets + 1)]
        for i in range(tickets + 1):
            shortest_path[i][start - 1] = 0
        g = defaultdict(list)
        h = []
        # Generate a map.
        for _ in range(edges):
            i, j, fare = map(int, input().split())
            g[i].append((j, fare))
            g[j].append((i, fare))
        # (price, vertices, remainder ticket)
        heapq.heappush(h, (0, start, tickets))

        while True:
            if 0 == len(h):
                break
            ori_price, vertex, remain_ticket = heapq.heappop(h)
            for v, price in g[vertex]:
                if shortest_path[remain_ticket][v - 1] > ori_price + price:
                    shortest_path[remain_ticket][v - 1] = min(shortest_path[remain_ticket][v - 1], ori_price + price)
                    heapq.heappush(h, (shortest_path[remain_ticket][v - 1], v, remain_ticket))
                if remain_ticket and shortest_path[remain_ticket - 1][v - 1] > ori_price + int(price / 2):
                    shortest_path[remain_ticket - 1][v - 1] = min(shortest_path[remain_ticket - 1][v - 1], ori_price + int(price / 2))
                    heapq.heappush(h, (shortest_path[remain_ticket - 1][v - 1], v, remain_ticket - 1))

        print(shortest_path[0][end - 1])


def main():
    input_data()

Submission status: Wrong Answer

Solution code:
""" Created by Jieyi on 10/31/16. """
import io
import sys
import heapq

# Simulate the redirect stdin.
from collections import defaultdict

if len(sys.argv) > 1:
    filename = sys.argv[1]
    inp = ''.join(open(filename, "r").readlines())
    sys.stdin = io.StringIO(inp)


def input_data():
    while True:
        tickets, vertices, edges, start, end = map(int, input().split())
        if 0 == tickets + vertices + edges + start + end:
            break

        shortest_path = [[sys.maxsize for _ in range(vertices + 1)] for _ in range(tickets + 1)]
        for i in range(tickets + 1):
            shortest_path[i][start] = 0
        g = defaultdict(list)
        h = []
        # Generate a map.
        for _ in range(edges):
            i, j, fare = map(int, input().split())
            g[i].append((j, fare))
            g[j].append((i, fare))
        # (price, vertices, remainder ticket)
        heapq.heappush(h, (0, start, tickets))

        while True:
            if 0 == len(h):
                break
            ori_price, vertex, remain_ticket = heapq.heappop(h)
            for v, price in g[vertex]:
                if shortest_path[remain_ticket][v] > ori_price + price:
                    shortest_path[remain_ticket][v] = min(shortest_path[remain_ticket][v], ori_price + price)
                    heapq.heappush(h, (shortest_path[remain_ticket][v], v, remain_ticket))
                if remain_ticket and shortest_path[remain_ticket - 1][v] > ori_price + int(price / 2):
                    shortest_path[remain_ticket - 1][v] = min(shortest_path[remain_ticket - 1][v], ori_price + int(price / 2))
                    heapq.heappush(h, (shortest_path[remain_ticket - 1][v], v, remain_ticket - 1))

        print(shortest_path[0][end])


def main():
    input_data()


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from heapq import *
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]])

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)

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

Submission status: Wrong Answer

Solution code:
from heapq import *
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]])

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=1e15
    dp=[]
    for i in range(c+1):
        temp=[INF for j in range(n+1)]
        dp.append(temp)

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

Submission status: Time Limit Exceeded

Solution code:

while True:
    c,n,m,s,d = list(map(int,input().split()))

    if c==0 and n == 0 and m == 0 and s == 0 and d == 0 : break

    f_list = [[ 0 for i in range(n+1)] for j in range(n+1)]
    path = {}
    for i in range(m):
        a,b,f = (list(map(int,input().split())))

        def add_path(a,b,f):
            global path
            global f_list
            if not a in path:
                path[a] = [b]
            else:
                path[a].append(b)
            f_list[a][b] = f

        add_path(a,b,f)
        add_path(b,a,f)

    #keiro tansaku
    stack = []
    stack.append(path[s])
    min_path  = None
    min_val = 999999999999

    work_val = []
    work_path = []
    def path_val(path):
        global c
        path.sort()
        v = 0
        if len(path) < c:
            v = sum(path) / 2
        else:
            v = sum(path[-c:])/2
            v += sum(path[:-c])

        return v
        
    work_path.append(s)
    work_val.append(0)

    while len(stack) > 0:


        ham = stack[-1]
        if len(ham) == 0:
            # 1階層上に
            stack.pop()
            work_val.pop()
            work_path.pop()
            continue

        next_p = ham.pop()

        if next_p in work_path: #already passed
            continue

        work_val.append(f_list[work_path[-1]][next_p])
        work_path.append(next_p)

        if next_p == d: #goal
            spam_val = path_val(work_val[:])
            if min(spam_val,min_val) != min_val:
                min_val = spam_val
            work_val.pop()
            work_path.pop()

        else:
            stack.append(path[next_p][:])

    print(int(min_val))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
#-*- coding:utf-8 -*-
import heapq

while True:
	# 割引券，駅，路線，スタート，ゴール
	c, n, m, s, d = map(int, raw_input().split())
	if not (c or n or m or s or d): break
	field = {}
	for i in xrange(m):
		a, b, f = map(int, raw_input().split())
		field[(a, b)] = f;
		field[(b, a)] = f;
	visited = set()
	q = []
	heapq.heappush(q, (0, c, -1, s))
	while q:
		cost, rem, frm, pos = heapq.heappop(q)
		if pos == d and (rem == 0 or (c > n and rem == c - n)):
			print cost
			break
		visited.add((rem, pos))
		for i in xrange(1, n + 1):
			edge = (pos, i)
			if edge in field:
				next = (rem, i)
				if not next in visited:
					heapq.heappush(q, (cost + field[edge], rem, pos, i))
				if rem > 0:
					next = (rem - 1, pos)
					if not next in visited:
						heapq.heappush(q, (cost + field[edge] / 2, rem - 1, pos, i))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
#-*- coding:utf-8 -*-
import heapq

while True:
	# 割引券，駅，路線，スタート，ゴール
	c, n, m, s, d = map(int, raw_input().split())
	if not (c or n or m or s or d): break
	field = {}
	for i in xrange(m):
		a, b, f = map(int, raw_input().split())
		field[(a, b)] = f;
		field[(b, a)] = f;
	visited = {}
	q = []
	heapq.heappush(q, (0, c, s))
	while q:
		cost, rem, pos = heapq.heappop(q)
		if pos == d:
			print cost
			break
		for i in xrange(1, n + 1):
			edge = (pos, i)
			if edge in field:
				next = (rem, i)
				ncost = cost + field[edge]
				if not next in visited or visited[next] < ncost:
					heapq.heappush(q, (ncost, rem, i))
					visited[next] = ncost
				if rem > 0:
					next = (rem - 1, pos)
					ncost = cost + field[edge] / 2
					if not next in visited or visited[next] < ncost:
						heapq.heappush(q, (ncost, rem - 1, i))
						visited[next] = ncost

Submission status: Accepted

Solution code:
from sys import stdin
from heapq import heappush,heappop

while(True):
    c,n,m,s,d = map(int, stdin.readline().split())
    if not c: break
    ma = [[] for _ in range(n)]
    s -= 1
    d -= 1
    for _ in range(m):
        a,b,f = map(int, stdin.readline().split())
        a -= 1
        b -= 1
        ma[a].append([f,b])
        ma[b].append([f,a])
    cost = [[10**10]*(c+1) for _ in range(n)]
    cost[s][c] = 0
    que = [[ cost[s][c], s, c ]]
    while que:
        co, pl, ti = heappop(que)
        for fee, town in ma[pl]:
            if cost[town][ti] > co+fee:
                cost[town][ti] = co+fee
                heappush(que,[cost[town][ti],town,ti])
            if ti and cost[town][ti-1] > co+fee//2:
                cost[town][ti-1] = co+fee//2
                heappush(que,[cost[town][ti-1],town,ti-1])
    print(min(cost[d]))

Submission status: Accepted

Solution code:
from sys import stdin
readline = stdin.readline



from collections import namedtuple
Runner = namedtuple('Runner', 'd v')

def main():
    while True:
        ticket, vertex, edge, start, destination = map(int, readline().split())
        if ticket == 0:
            break

        start -= 1
        destination -= 1
        g = defaultdict(list)
        for i in range(edge):
            s, t, length = map(int, readline().split())
            s -= 1
            t -= 1
            g[s].append((length, t))
            g[t].append((length, s))
        
        d = ex_dijkstra(g, vertex, start, ticket)
        print(min(d[destination]))



from heapq import heappush, heappop
from collections import defaultdict
def ex_dijkstra(g, size, start, ticket):
    d = [[float('inf')] * (ticket + 1) for i in range(size)]
    d[start][ticket] = 0
    heap = [(d[start][ticket], start, ticket)]
    while heap:
        du, u, ticket = heappop(heap)
        for length, v in g[u]:
            if d[v][ticket] > du + length:
                d[v][ticket] = du + length
                heappush(heap,(d[v][ticket], v, ticket))
            if ticket and d[v][ticket - 1] > du + length // 2:
                d[v][ticket - 1] = du + length // 2
                heappush(heap,(d[v][ticket - 1], v, ticket - 1))

    return d

main()

Submission status: Accepted

Solution code:
total = 0
ticket = 1
def f(p, cost, route):
    for k, c in data.items():
        a, b = k
        if a == p:
            if not b in route:
                value1, value2 = dis(p, c, cost)
                if not b in cost or value1 < cost[b][total]:
                    cost[b] = [value1, value2]
        elif b == p:
            if not a in route:
                value1, value2 = dis(p, c, cost)
                if not a in cost or value1 < cost[a][total]:
                    cost[a] = [value1, value2]
    else:
        del cost[p]
    b, c = sorted(cost.items(), key=lambda x: x[1])[0]
    if b == g:
        print cost[g][total]
    else:
        route.append(b)
        f(b, cost, route)
        
def dis(p, c, cost):
    lis = cost[p][ticket][:]
    if len(cost[p][ticket]) != t:
        value1 = cost[p][total]+c/2
        lis.append(c)
        value2 = lis
    else:
        mini = sorted(cost[p][ticket])[0]
        if mini < c:
            value1 = cost[p][total]+(mini/2)+(c/2)
            lis.remove(mini)
            lis.append(c)
            value2 = lis
        else:
            value1 = cost[p][total]+c
            value2 = lis
    return value1, value2
        
while True:
    t, n, m, s, g = map(int, raw_input().split())
    if t == n == m == s == g == 0: break
    data = {}
    for i in range(m):
        a, b, c = map(int, raw_input().split())
        data[(a, b)] = c
    else:
        f(s, cost={s:[0, []]}, route=[s])

Submission status: Accepted

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 or node == sys.maxint:
      return cost
    defnode[node] = True
    for i in xrange(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(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: Accepted

Solution code:
""" Created by Jieyi on 10/31/16. """
import io
import sys
import heapq

# Simulate the redirect stdin.
from collections import defaultdict

if len(sys.argv) > 1:
    filename = sys.argv[1]
    inp = ''.join(open(filename, "r").readlines())
    sys.stdin = io.StringIO(inp)


def input_data():
    while True:
        tickets, vertices, edges, start, end = map(int, input().split())
        if 0 == tickets + vertices + edges + start + end:
            break

        shortest_path = [[sys.maxsize for _ in range(vertices + 1)] for _ in range(tickets + 1)]
        for i in range(tickets + 1):
            shortest_path[i][start] = 0
        g = defaultdict(list)
        h = []
        # Generate a map.
        for _ in range(edges):
            i, j, fare = map(int, input().split())
            g[i].append((j, fare))
            g[j].append((i, fare))
        # (price, vertices, remainder ticket)
        heapq.heappush(h, (0, start, tickets))

        while True:
            if 0 == len(h):
                break
            ori_price, vertex, remain_ticket = heapq.heappop(h)
            for v, price in g[vertex]:
                if shortest_path[remain_ticket][v] > ori_price + price:
                    shortest_path[remain_ticket][v] = min(shortest_path[remain_ticket][v], ori_price + price)
                    heapq.heappush(h, (shortest_path[remain_ticket][v], v, remain_ticket))
                if remain_ticket and shortest_path[remain_ticket - 1][v] > ori_price + int(price / 2):
                    shortest_path[remain_ticket - 1][v] = min(shortest_path[remain_ticket - 1][v], ori_price + int(price / 2))
                    heapq.heappush(h, (shortest_path[remain_ticket - 1][v], v, remain_ticket - 1))

        cheapest = sys.maxsize
        for i in range(tickets):
            cheapest = min(shortest_path[i][end], cheapest)
        print(cheapest)


def main():
    input_data()


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
INF = 10000000

def bf(es, dist, c, s, d):
    dist[s][0] = 0

    isUpdated = True
    while isUpdated:
        isUpdated = False
        for e in es:
            a, b, f = e
            for i in range(c+1):
                if dist[a][i] != INF and dist[a][i] + f < dist[b][i]:
                    dist[b][i] = dist[a][i] + f
                    isUpdated = True
                if dist[a][i] != INF and (i+1) <= c and dist[a][i] + f / 2 < dist[b][i+1]:
                    dist[b][i+1] = dist[a][i] + int(f / 2)
                    isUpdated = True
    
    return min(dist[d])

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

        s -= 1
        d -= 1
        es = []
        dist = [[INF for _ in range(c+1)] for __ in range(n)] # dist[i][j]: ???i?????§????????????j????????£??????????????????
        for _ in range(m):
            a, b, f = map(int, input().split())
            a -= 1
            b -= 1
            es.append([a, b, f])
            es.append([b, a, f])

        print(bf(es, dist, c, s, d))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
INF = 10 ** 20

while True:
  c, n, m, s, d = map(int, input().split())
  s -= 1
  d -= 1
  if c == 0:
    break
  edges = [[] for _ in range(n * (c + 1))]
  for _ in range(m):
    a, b, f = map(int, input().split())
    a -= 1
    b -= 1
    for i in range(c + 1):
      edges[a + i * n].append((b + i * n, f))
      edges[b + i * n].append((a + i * n, f))
      if i != c:
        edges[a + i * n].append((b + (i + 1) * n, f // 2))
        edges[b + i * n].append((a + (i + 1) * n, f // 2))
  for i in range(c):
    edges[d + i * n].append((d + (i + 1) * n, 0))

  cost = [INF] * (n * (c + 1))
  que = []
  heappush(que, (0, s))
  while que:
    total, point = heappop(que)
    for to, fee in edges[point]:
      if cost[to] > total + fee:
        cost[to] = total + fee
        heappush(que, (total + fee, to))
  print(cost[d + n * c])

Submission status: Accepted

Solution code:
#!/usr/bin/env python
#-*- coding:utf-8 -*-
import heapq

while True:
	# 割引券，駅，路線，スタート，ゴール
	c, n, m, s, d = map(int, raw_input().split())
	if not (c or n or m or s or d): break
	field = {}
	for i in xrange(m):
		a, b, f = map(int, raw_input().split())
		field[(a, b)] = field[(b, a)] = f;
	visited = {}
	q = []
	heapq.heappush(q, (0, c, s))
	while q:
		cost, rem, pos = heapq.heappop(q)
		if pos == d:
			print cost
			break
		for i in xrange(1, n + 1):
			edge = (pos, i)
			next = (rem, i)
			ncost = cost + field.get(edge, 0x7fffffff)
			if ncost < visited.get(next, 0x7fffffff):
				heapq.heappush(q, (ncost, rem, i))
				visited[next] = ncost
			next = (rem - 1, i)
			ncost = cost + field.get(edge, 0x7fffffff) / 2
			if rem > 0 and ncost < visited.get(next, 0x7fffffff):
				heapq.heappush(q, (ncost, rem - 1, i))
				visited[next] = ncost