結果
問題 | No.2565 はじめてのおつかい |
ユーザー |
|
提出日時 | 2023-12-02 16:12:28 |
言語 | Crystal (1.14.0) |
結果 |
AC
|
実行時間 | 375 ms / 2,000 ms |
コード長 | 2,922 bytes |
コンパイル時間 | 14,309 ms |
コンパイル使用メモリ | 295,568 KB |
実行使用メモリ | 55,448 KB |
最終ジャッジ日時 | 2024-09-26 19:58:26 |
合計ジャッジ時間 | 23,166 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
main = -> {n, m = read_line.split.map &.to_i64graph = NgLib::BfsGraph.new(3 * n)graph2 = NgLib::BfsGraph.new(3 * n)m.times dou, v = read_line.split.map &.to_i64.predgraph.add_edge(u, v, directed: true)graph.add_edge(u + n, v + n, directed: true)graph.add_edge(u + 2*n, v + 2*n, directed: true)graph2.add_edge(u, v, directed: true)graph2.add_edge(u + n, v + n, directed: true)graph2.add_edge(u + 2*n, v + 2*n, directed: true)endgraph.add_edge(n - 2, n - 2 + n, directed: true)graph.add_edge(n - 1 + n, n - 1 + 2*n, directed: true)graph2.add_edge(n - 1, n - 1 + n, directed: true)graph2.add_edge(n - 2 + n, n - 2 + 2*n, directed: true)d = Math.min(graph.shortest_path(0, 0 + 2*n), graph2.shortest_path(0, 0 + 2*n))puts d >= OO ? -1 : d - 2}main.callOO = (1_i64 << 62) - (1_i64 << 31)module NgLib# $n$ 頂点 $m$ 辺からなるグラフに対して、幅優先探索によって最短経路を求めます。## 経路の復元も可能です。class BfsGraphgetter size : Int32getter graph : Array(Array(Int32))# $n$ 頂点 $0$ 辺からなるグラフを作成します。## ```# graph = BfsGraph.new(n)# ```def initialize(n : Int)@size = n.to_i64.to_i32@graph = Array.new(@size) { Array(Int32).new }end# 辺 $(u, v)$ を追加します。## `directed` が `true` の場合、# 有向辺とみなして、$u$ から $v$ への辺のみ生やします。## ```# graph = BfsGraph.new(n)# graph.add_edge(u, v) # => (u) <---w---> (v)# graph.add_edge(u, v, directed: true) # => (u) ----w---> (v)# ```def add_edge(u : Int, v : Int, directed : Bool = false)@graph[u.to_i32] << v.to_i32@graph[v.to_i32] << u.to_i32 unless directedend# 全点対間の最短経路長を返します。## ```# dists = graph.shortest_path# dists # => [[0, 1, 3], [1, 0, 2], [1, 1, 0]]# ```def shortest_path(0...@size).map { |s| shortest_path(s) }end# 始点 `start` から各頂点への最短経路長を返します。## ```# dist = graph.shortest_path(start: 2)# dist # => [3, 8, 0, 7, 1]# ```def shortest_path(start : Int)queue = Deque.new([start.to_i32])dist = Array.new(@size) { |i| i == start ? 0_i64 : OO }until queue.empty?from = queue.shift@graph[from].each do |to|next if dist[to] != OOdist[to] = dist[from] + 1queue << toendenddistend# 始点 `start` から終点 `dest` への最短経路長を返します。## ```# dist = graph.shortest_path(start: 2, dest: 0)# dist # => 12# ```def shortest_path(start : Int, dest : Int)shortest_path(start)[dest]endendend