結果

問題 No.1812 Uribo Road
コンテスト
ユーザー titia
提出日時 2022-01-18 00:58:12
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 2,983 ms / 5,000 ms
コード長 1,540 bytes
コンパイル時間 265 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 354,688 KB
最終ジャッジ日時 2024-11-23 13:05:51
合計ジャッジ時間 27,810 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline
import heapq

N,M,K=map(int,input().split())
R=list(map(int,input().split()))

EX=[tuple(map(int,input().split())) for i in range(M)]

E=[[] for i in range(N+1)]

for a,b,c in EX:
    E[a].append((b,c))
    E[b].append((a,c))

for i in range(K):
    R[i]-=1

def dijk(x):
    DIS=[1<<63]*(N+1)

    Q=[(0,x)]
    DIS[x]=0

    while Q:
        time,now=heapq.heappop(Q)

        if DIS[now]<time:
            continue

        for to,cost in E[now]:
            if DIS[to]>DIS[now]+cost:
                DIS[to]=DIS[now]+cost
                heapq.heappush(Q,(DIS[to],to))

    return DIS

DIST=[[] for i in range(N+1)]

DIST[1]=dijk(1)
DIST[N]=dijk(N)

R2=[]

for i in range(K):
    r=R[i]
    x,y,cc=EX[r]

    R2.append((x,y,cc))

    DIST[x]=dijk(x)
    DIST[y]=dijk(y)

#print(DIST)

DP=[[1<<63]*(1<<K) for i in range(N+1)]

DP[1][0]=0
Q=[(0,1,0)]

while Q:
    time,now,b=heapq.heappop(Q)

    if DP[now][b]<time:
        continue

    for i in range(K):
        if b & (1<<i) ==0:
            x,y,c=R2[i]

            if DP[y][b|(1<<i)]>DP[now][b]+DIST[now][x]+c:
                DP[y][b|(1<<i)]=DP[now][b]+DIST[now][x]+c
                heapq.heappush(Q,(DP[y][b|(1<<i)],y,b|(1<<i)))

            if DP[x][b|(1<<i)]>DP[now][b]+DIST[now][y]+c:
                DP[x][b|(1<<i)]=DP[now][b]+DIST[now][y]+c
                heapq.heappush(Q,(DP[x][b|(1<<i)],x,b|(1<<i)))

ANS=1<<63

for i in range(N+1):
    xx=DP[i][-1]

    if xx==1<<63:
        continue

    ANS=min(ANS,xx+DIST[i][N])

print(ANS)
0