結果
問題 | No.1065 電柱 / Pole (Easy) |
ユーザー |
![]() |
提出日時 | 2020-05-29 22:39:25 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 1,688 ms / 2,000 ms |
コード長 | 1,013 bytes |
コンパイル時間 | 98 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 124,928 KB |
最終ジャッジ日時 | 2024-11-06 06:28:47 |
合計ジャッジ時間 | 34,230 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 46 |
ソースコード
import sys from math import sqrt from heapq import heappush, heappop INF = 10**10 input = sys.stdin.readline def main(): N, M = map(int,input().split()) X, Y = map(int,input().split()) X -= 1 Y -= 1 D = [] for _ in range(N): D.append(list(map(int,input().split()))) K = [[] for _ in range(N)] for _ in range(M): P, Q = map(int,input().split()) P -= 1 Q -= 1 K[P].append((Q,sqrt((D[P][0]-D[Q][0])**2+(D[P][1]-D[Q][1])**2))) K[Q].append((P,sqrt((D[P][0]-D[Q][0])**2+(D[P][1]-D[Q][1])**2))) dist = [INF] * N def dijkstra(N, G, s): que = [(0, s)] dist[s] = 0 while que: c, v = heappop(que) if dist[v] < c: continue for t, cost in G[v]: if dist[v] + cost < dist[t]: dist[t] = dist[v] + cost heappush(que, (dist[t], t)) dijkstra(N, K, X) print(dist[Y]) if __name__ == '__main__': main()