結果
| 問題 | No.3810 Binary Shortest Path Query |
| コンテスト | |
| ユーザー |
回転
|
| 提出日時 | 2026-11-22 12:26:33 |
| 言語 | PyPy3 (8.0.1 + ACL) |
| 結果 |
WA
不安定
|
| 実行時間 | - |
| コード長 | 1,091 bytes |
| 記録 | |
| コンパイル時間 | 122 ms |
| コンパイル使用メモリ | 64,064 KB |
| 実行使用メモリ | 97,000 KB |
| 最終ジャッジ日時 | 2026-11-22 12:26:59 |
| 合計ジャッジ時間 | 24,840 ms |
|
ジャッジサーバーID (参考情報) |
judge5_0 / judge1_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 28 WA * 2 |
ソースコード
import heapq
from collections import defaultdict
N,M,Q = list(map(int,input().split()))
S = list(map(int,input().split()))
edge = [[] for _ in range(N)]
for i in range(M):
u,v,w = list(map(int,input().split()))
u -= 1;v -= 1
if(i > 63):continue
if(w * (1<<(i+1)) > 2*10**18):continue
edge[u].append((v, w * (1<<(i+1))))
edge[v].append((u, w * (1<<(i+1))))
INF = 3*10**18
dist_from_warp = [INF] * N
q = [(S[i], i) for i in range(N)]
heapq.heapify(q)
while(q):
v,now = heapq.heappop(q)
if(dist_from_warp[now] <= v):continue
dist_from_warp[now] = v
for i,w in edge[now]:
heapq.heappush(q, (v + w, i))
for _ in range(Q):
a,b = list(map(int,input().split()))
a -= 1;b -= 1
ans = dist_from_warp[a] + dist_from_warp[b]
q = [(0,a)]
dist = defaultdict(lambda:INF)
while(q):
v,now = heapq.heappop(q)
if(now == b):
ans = min(ans, v)
break
if(dist[now] <= v):continue
dist[now] = v
for i,w in edge[now]:
heapq.heappush(q, (v+w, i))
print(ans)
回転