結果

問題 No.3111 Toll Optimization
コンテスト
ユーザー Sinonen
提出日時 2025-04-18 22:27:09
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,226 ms / 5,000 ms
コード長 739 bytes
コンパイル時間 456 ms
コンパイル使用メモリ 82,564 KB
実行使用メモリ 230,536 KB
最終ジャッジ日時 2025-04-18 22:27:49
合計ジャッジ時間 34,081 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 70
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict
import heapq
N,M,K=list(map(int,input().split()))
C=list(map(int,input().split()))
path=defaultdict(list)
for i in range(M):
	u,v=list(map(int,input().split()))
	u-=1
	v-=1
	for j in range(K+1):
		path[u+N*j].append((C[i],v+N*j))
		path[v+N*j].append((C[i],u+N*j))
	for j in range(K):
		path[u+N*j].append((0,v+N*j+N))
		path[v+N*j].append((0,u+N*j+N))
		
dist=[10**18]*(N*K+N)
dist[0]=0
Q=[]
heapq.heapify(Q)
check=set()
heapq.heappush(Q,(0,0))
while len(Q)>0:
	d,p=heapq.heappop(Q)
	if p in check:
		continue
	check.add(p)
	for c,j in path[p]:
		if dist[j]>d+c:
			dist[j]=d+c
			heapq.heappush(Q,(d+c,j))
ans=10**18
for i in range(K+1):
	ans=min(ans,dist[N*i+N-1])
if ans>10**17:
	ans=-1
print(ans)
0