結果
問題 | No.1065 電柱 / Pole (Easy) |
ユーザー |
![]() |
提出日時 | 2020-05-29 22:28:59 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 1,626 ms / 2,000 ms |
コード長 | 776 bytes |
コンパイル時間 | 162 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 103,376 KB |
最終ジャッジ日時 | 2024-11-06 05:51:39 |
合計ジャッジ時間 | 33,635 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 46 |
ソースコード
import sys from heapq import heappop, heappush read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines N, M = map(int, readline().split()) S, T = map(int, readline().split()) X = [complex(0, 0)] * (N + 1) for i in range(1, N + 1): p, q = map(int, readline().split()) X[i] = complex(p, q) G = [[] for _ in range(N + 1)] m = map(int, read().split()) for p, q in zip(m, m): d = abs(X[p] - X[q]) G[p].append((q, d)) G[q].append((p, d)) INF = 10.0**18 dist = [INF] * (N+1) q = [(0, S)] dist[S] = 0 while q: dv, v = heappop(q) if dv != dist[v]: continue for w, d in G[v]: dw = dv + d if dist[w] > dw: dist[w] = dw heappush(q, (dw, w)) print(dist[T])