結果
問題 |
No.1065 電柱 / Pole (Easy)
|
ユーザー |
|
提出日時 | 2020-05-29 21:59:51 |
言語 | Ruby (3.4.1) |
結果 |
AC
|
実行時間 | 1,536 ms / 2,000 ms |
コード長 | 515 bytes |
コンパイル時間 | 259 ms |
コンパイル使用メモリ | 7,552 KB |
実行使用メモリ | 47,872 KB |
最終ジャッジ日時 | 2024-11-06 18:35:41 |
合計ジャッジ時間 | 30,366 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 46 |
コンパイルメッセージ
Syntax OK
ソースコード
n, m = gets.to_s.split.map{|t| t.to_i } x, y = gets.to_s.split.map{|t| t.to_i - 1 } xys = Array.new(n){ gets.to_s.split.map{|t| t.to_i } } g = Array.new(n){ [] } m.times do s, t = gets.to_s.split.map{|t| t.to_i - 1 } g[s] << t g[t] << s end inf = Float::INFINITY d = [inf] * n d[x] = 0 q = [x] while ( v = q.shift ) d_v = d[v] g[v].each do |u| t = Math.hypot( xys[u][0] - xys[v][0], xys[u][1] - xys[v][1] ) if d[u] > d_v + t d[u] = d_v + t q.push u end end end puts d[y]