結果

問題 No.3111 Toll Optimization
ユーザー 芋
提出日時 2025-04-19 20:23:34
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 2,967 ms / 5,000 ms
コード長 4,390 bytes
コンパイル時間 446 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 65,336 KB
最終ジャッジ日時 2025-04-19 20:24:53
合計ジャッジ時間 68,016 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 70
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math
from copy import deepcopy as dc
#sys.setrecursionlimit(10 ** 6)
from collections import defaultdict as dd
import heapq
from itertools import permutations as per
_S = input;_R = range;_P = print
def _RR(a): return range(a-1,-1,-1)
def _I(): return int(_S())
def _M(): return map(int, _S().split())
def _L(): return list(_M())
def _T(): return tuple(_L())
def _O(): return list(map(int, open(0).read().split()))
def yn(b): print("Yes" if b else "No")
def fs(b): print("First" if b else "Second")
biga = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";smaa = "abcdefghijklmnopqrstuvwxyz"
ctoi = lambda c: ord(c) - ord('a')
ctoi2 = lambda c: ord(c) - ord('A')
itoc = lambda i: chr(ord('a') + i)
itoc2 = lambda i: chr(ord('A') + i)
inf = 10 ** 18
mod = 998244353
def around(x,y,type_=False):
    rt = []
    rt.extend([(x+1,y),(x-1,y),(x,y+1),(x,y-1)])
    if type_:
        rt.extend([(x+1,y+1),(x-1,y-1),(x-1,y+1),(x+1,y-1)])
    return rt
def acc(a):
    b = [0]
    for i in a:
        b.append(b[-1] + i)
    return b
class heap:
    l = []
    def __init__(self,*s): self.l = list(s);heapq.heapify(self.l)
    def min(self): return False if (len(self.l) == 0) else self.l[0]
    def pop(self): return False if (len(self.l) == 0) else heapq.heappop(self.l)
    def push(self,n): heapq.heappush(self.l,n)
    def dump(self): return heapq.nsmallest(len(self.l),self.l)
    def max(self): return False if (len(self.l) == 0) else heapq.nlargest(1,self.l)[0]
    def len(self): return len(self.l)
class base:
    bn = 0; dig = 0; num = []
    def __init__(self,base_num,digit = 0):
        self.bn = base_num; self.dig = digit; self.num = [0]*digit
    def max(self): return(self.bn**self.dig-1)
    def dump(self): return(self.num[::-1])
    def ncp(self,digit,n): self.num[digit] = min(self.num[digit]+n,self.bn-1)
    def plus(self,digit,n):
        for i in _R(digit-self.dig+1): self.num.append(0)
        self.dig = max(self.dig,digit+1)
        if (self.num[digit]+n >= self.bn):
            self.plus(digit+1,(self.num[digit]+n)//self.bn)
        self.num[digit] = (self.num[digit]+n)%self.bn
    def copy(self,n):
        self.num = dc(n)
        dig = len(self.num)
    def change(self,n):
        digit = int(math.log(n,self.bn))if n!=0 else 0+1
        for i in _R(digit-self.dig+1): self.num.append(0)
        self.dig = max(self.dig,digit+1)
        for i in _R(self.dig):
            self.num[i] = n%self.bn**(i+1)//self.bn**i
            n -= self.num[i]
        return self.dump()
    def b10(self): return(sum([self.num[i]*self.bn**i for i in _R(self.dig)]))
def gin(N, M=None):
    g = [[] for _ in range(N)]
    for _ in range(N-1 if M is None else M):
        u, v = map(int, input().split());u -= 1;v -= 1
        g[u].append(v);g[v].append(u)
    return g
def ginh(N, M):
    g = [[] for _ in range(N)]
    for i in range(M):
        u, v = map(int, input().split());u -= 1;v -= 1
        g[u].append((v,i));g[v].append((u,i))
    return g
#from atcoder.segtree import SegTree
def ub(lis,n,same=False):
    l = 0
    r = len(lis)
    while r-l>1:
        m = (l+r)//2
        if (lis[m]>n):
            r = m
        else:
            l = m
    return l
def msum(a, b):
    return (a + b)
class rhash:
    hs = None
    def __init__(self,S,N):
        self.hs = SegTree(msum,0,[ctoi(S[i])*pow(31,i,mod) for i in _R(N)])
    def get(self,l,r):
        return self.hs.prod(l,r+1)*pow(pow(31,l,mod),mod-2,mod)%mod
    def getall(self):
        return self.hs.all_prod()
    def change(self,n,c):
        self.hs.set(n,ctoi(c)*pow(31,n,mod))
def nwse(s,x,y,rev=False):
    if (rev):
        s = {"N":"S","S":"N","W":"E","E":"W"}[s]
    if s=="N": return (x-1,y)
    elif s=="W": return (x,y-1)
    elif s=="S": return (x+1,y)
    elif s=="E": return (x,y+1)
#--------------ごっつりしていってね--------------
#あぁそうそう　ごちうさ楽しみ
N,M,K = _M()
C = _L()
g = ginh(N,M)
hv = [[inf]*N for i in _R(K+1)]
hv[0][0] = 0
p = heap((0,0,0))
while p.len():
    h,d,k = p.pop()
    if (hv[k][d] != h): continue
    for i,w in g[d]:
        if (hv[k][i] > hv[k][d]+C[w]):
            hv[k][i] = hv[k][d]+C[w]
            p.push((hv[k][i],i,k))
        if k < K and (hv[k+1][i] > hv[k][d]):
            hv[k+1][i] = hv[k][d]
            p.push((hv[k+1][i],i,k+1))
ans = inf
for i in _R(K+1):
    ans = min(hv[i][N-1],ans)
print (-1 if ans == inf else ans)
0