結果
| 問題 | No.3810 Binary Shortest Path Query |
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2026-11-20 23:22:53 |
| 言語 | PyPy3 (8.0.1 + ACL) |
| 結果 |
WA
不安定
|
| 実行時間 | - |
| コード長 | 1,335 bytes |
| 記録 | |
| コンパイル時間 | 89 ms |
| コンパイル使用メモリ | 64,340 KB |
| 実行使用メモリ | 92,700 KB |
| 最終ジャッジ日時 | 2026-11-20 23:23:04 |
| 合計ジャッジ時間 | 10,890 ms |
|
ジャッジサーバーID (参考情報) |
judge2_0 / judge5_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 21 WA * 3 RE * 6 |
ソースコード
# https://github.com/robe2222555/atcoder-lib/blob/main/template/python/main.py
import sys
input = lambda: sys.stdin.readline().rstrip()
def LI(): return list(map(int, input().split()))
def II(): return int(input())
INF = 1<<60
def solve():
N,M,Q = LI()
S = [0] + LI()
G = [[] for _ in range(N+1)]
LIM = max(S)*2-1
E = []
for i in range(1, M+1):
# w<<i <= LIM
# 1<<i <= LIM/w
u,v,w = LI()
if i <= (LIM//w).bit_length()-1:
E.append((u,v,w<<i))
# 全点対最短経路
V = set()
for u,v,w in E:
V.add(u)
V.add(v)
V = list(V)
K = len(V)
compress = {V[i]:i for i in range(K)}
assert len(V)<200
dis = [[INF]*K for _ in range(K)]
for i in range(K):
dis[i][i] = 0
for u,v,w in E:
dis[compress[u]][compress[v]] = w
dis[compress[v]][compress[u]] = w
for k in range(K):
for u in range(K):
for v in range(K):
dis[u][v] = min(dis[u][v], dis[u][k] + dis[k][v])
for _ in range(Q):
a,b = LI()
ans = S[a] + S[b]
if (a in V) and (b in V):
ans = min(ans, dis[compress[a]][compress[b]])
if a in V:
for i in range(K):
ans = min(ans, dis[compress[a]][i] + S[V[i]] + S[b])
if b in V:
for i in range(K):
ans = min(ans, S[a] + S[V[i]] + dis[i][compress[b]])
print(ans)
return
def main():
T = 1
for _ in range(T):
solve()
return
if __name__ == '__main__':
main()