syuntoku14の進捗

進捗を書きなぐります

AOJでPythonに慣れる(15問目)

問題
Highway Express Bus

所感
・良い問題やこれは…
・DPをうまく使うと解ける(私は解けない)
・いつもみたいにsample inputに対してはいい感じの答え出すけどWA(test case全部表示してほちい…)

コード

from heapq import *
import copy 
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,used]
    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(dp[c][d])

よく考えたら今までちゃんとACしたことない...