結果
問題 |
No.1065 電柱 / Pole (Easy)
|
ユーザー |
|
提出日時 | 2022-10-23 03:34:15 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,018 ms / 2,000 ms |
コード長 | 731 bytes |
コンパイル時間 | 163 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 142,740 KB |
最終ジャッジ日時 | 2024-07-02 00:44:48 |
合計ジャッジ時間 | 25,827 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 46 |
ソースコード
import heapq import math INF = 1e15 n, m = map(int, input().split()) src, dst = map(int, input().split()) src -= 1 dst -= 1 points = [list(map(int, input().split())) for _ in range(n)] g = [[] for _ in range(n)] for _ in range(m): u, v = map(int, input().split()) u -= 1 v -= 1 xu, yu = points[u] xv, yv = points[v] d = math.sqrt((xv - xu) ** 2 + (yv - yu) ** 2) g[u].append((v, d)) g[v].append((u, d)) dist = [INF for _ in range(n)] dist[src] = 0.0 hp = [(0.0, src)] while len(hp) > 0: cd, cur = heapq.heappop(hp) if cd > dist[cur]: continue for nxt, cost in g[cur]: if dist[cur] + cost < dist[nxt]: dist[nxt] = dist[cur] + cost heapq.heappush(hp, (dist[nxt], nxt)) print(dist[dst])