結果

問題 No.3111 Toll Optimization
コンテスト
ユーザー howard127
提出日時 2025-04-19 13:03:47
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 633 bytes
コンパイル時間 272 ms
コンパイル使用メモリ 12,416 KB
実行使用メモリ 63,992 KB
最終ジャッジ日時 2025-04-19 13:04:21
合計ジャッジ時間 31,120 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 53 WA * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq as h
g={}
n,m,k=map(int,input().split())
c=list(map(int,input().split()))
for i in range(1,n+1):g[str(i)]={}
for i in range(m):
 u,v=input().split()
 g[u][v]=g[v][u]=c[i]
s="1";e=str(n)
d={i:float('inf')for i in g};d[s]=0
p={i:None for i in g}
q=[(0,s)]
while q:
 cd,cn=h.heappop(q)
 if cd>d[cn]:continue
 if cn==e:break
 for nb,w in g[cn].items():
  di=cd+w
  if di<d[nb]:d[nb]=di;p[nb]=cn;h.heappush(q,(di,nb))
if d[e]==float('inf'):print(-1)
else:
 pe=[]
 c=e
 while c!=s:
  pr=p[c]
  pe.append((pr,c,g[pr][c]))
  c=pr
 pe.sort(key=lambda x:x[2],reverse=True)
 tk=pe[:min(k,len(pe))]
 print(d[e]-sum(e[2]for e in tk))
0