結果
| 問題 | No.3810 Binary Shortest Path Query |
| コンテスト | |
| ユーザー |
sepa38
|
| 提出日時 | 2026-11-18 15:23:42 |
| 言語 | PyPy3 (8.0.1 + ACL) |
| 結果 |
TLE
不安定
|
| 実行時間 | - |
| コード長 | 1,085 bytes |
| 記録 | |
| コンパイル時間 | 109 ms |
| コンパイル使用メモリ | 64,088 KB |
| 実行使用メモリ | 195,808 KB |
| 最終ジャッジ日時 | 2026-11-20 20:54:12 |
| 合計ジャッジ時間 | 7,622 ms |
|
ジャッジサーバーID (参考情報) |
judge1_0 / judge2_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 12 TLE * 1 -- * 17 |
ソースコード
# 愚直解: 辺コストを多倍長で正確に計算し、ワープを完全グラフの辺として Dijkstra
import sys, heapq
def solve(inp):
d = inp.split(); p = 0
N, M, Q = int(d[0]), int(d[1]), int(d[2]); p = 3
S = [int(x) for x in d[p:p+N]]; p += N
g = [[] for _ in range(N)]
for i in range(1, M+1):
u, v, w = int(d[p])-1, int(d[p+1])-1, int(d[p+2]); p += 3
c = w << i
g[u].append((v, c)); g[v].append((u, c))
out = []
for _ in range(Q):
a, b = int(d[p])-1, int(d[p+1])-1; p += 2
dist = [None]*N; dist[a] = 0; pq = [(0, a)]
while pq:
du, u = heapq.heappop(pq)
if du != dist[u]: continue
nb = list(g[u]) + [(x, S[u]+S[x]) for x in range(N) if x != u]
for v, c in nb:
nd = du + c
if dist[v] is None or nd < dist[v]:
dist[v] = nd; heapq.heappush(pq, (nd, v))
out.append(dist[b])
return "\n".join(map(str, out)) + "\n"
if __name__ == "__main__":
sys.stdout.write(solve(sys.stdin.read()))
sepa38