結果
問題 | No.1812 Uribo Road |
ユーザー | titia |
提出日時 | 2022-01-18 00:58:12 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 3,454 ms / 5,000 ms |
コード長 | 1,540 bytes |
コンパイル時間 | 283 ms |
コンパイル使用メモリ | 13,184 KB |
実行使用メモリ | 354,688 KB |
最終ジャッジ日時 | 2024-05-02 19:08:10 |
合計ジャッジ時間 | 30,635 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 31 ms
10,880 KB |
testcase_01 | AC | 33 ms
10,880 KB |
testcase_02 | AC | 34 ms
10,880 KB |
testcase_03 | AC | 432 ms
12,800 KB |
testcase_04 | AC | 33 ms
10,880 KB |
testcase_05 | AC | 32 ms
10,752 KB |
testcase_06 | AC | 33 ms
10,880 KB |
testcase_07 | AC | 60 ms
11,136 KB |
testcase_08 | AC | 61 ms
11,776 KB |
testcase_09 | AC | 75 ms
12,544 KB |
testcase_10 | AC | 59 ms
12,032 KB |
testcase_11 | AC | 48 ms
11,392 KB |
testcase_12 | AC | 2,413 ms
351,104 KB |
testcase_13 | AC | 2,237 ms
351,360 KB |
testcase_14 | AC | 2,207 ms
350,080 KB |
testcase_15 | AC | 424 ms
20,736 KB |
testcase_16 | AC | 762 ms
91,904 KB |
testcase_17 | AC | 1,895 ms
170,112 KB |
testcase_18 | AC | 836 ms
24,448 KB |
testcase_19 | AC | 3,252 ms
348,288 KB |
testcase_20 | AC | 3,454 ms
348,160 KB |
testcase_21 | AC | 3,190 ms
354,688 KB |
testcase_22 | AC | 2,757 ms
353,664 KB |
testcase_23 | AC | 160 ms
14,592 KB |
testcase_24 | AC | 33 ms
11,008 KB |
testcase_25 | AC | 152 ms
16,384 KB |
testcase_26 | AC | 44 ms
11,264 KB |
testcase_27 | AC | 425 ms
19,840 KB |
testcase_28 | AC | 294 ms
19,712 KB |
testcase_29 | AC | 32 ms
10,752 KB |
testcase_30 | AC | 71 ms
12,032 KB |
testcase_31 | AC | 1,749 ms
147,840 KB |
testcase_32 | AC | 74 ms
11,136 KB |
testcase_33 | AC | 1,239 ms
178,432 KB |
ソースコード
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)