#679380 (Crystal) No.1607 Kth Maximum Card

• 問題: No.1607 Kth Maximum Card
• ユーザー: yuruhiya
• 提出日時: 2021-07-17 14:21:54
• 言語: Crystal (1.14.0)
• 結果: AC
• 実行時間: 575 ms / 3,500 ms
• コード長: 7,233 bytes
• コンパイル時間: 12,460 ms
• コンパイル使用メモリ: 293,956 KB
• 実行使用メモリ: 29,264 KB
• 最終ジャッジ日時: 2024-07-07 02:08:00
• 合計ジャッジ時間: 20,651 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

ファイルパターン	結果
sample	AC * 3
other	AC * 33

ソースコード

# require "/graph/bfs01"
# require "../graph"
struct Edge(T)
  include Comparable(Edge(T))

  property to : Int32, cost : T

  def initialize(@to : Int32, @cost : T)
  end

  def <=>(other : Edge(T))
    {cost, to} <=> {other.cost, other.to}
  end

  def to_s(io) : Nil
    io << '(' << to << ", " << cost << ')'
  end

  def inspect(io) : Nil
    io << "->#{to}(#{cost})"
  end
end

struct Edge2(T)
  include Comparable(Edge2(T))

  property from : Int32, to : Int32, cost : T

  def initialize(@from : Int32, @to : Int32, @cost : T)
  end

  def <=>(other : Edge2(T))
    {cost, from, to} <=> {other.cost, other.from, other.to}
  end

  def reverse
    Edge2(T).new(to, from, cost)
  end

  def sort
    Edge2(T).new(*{to, from}.minmax, cost)
  end

  def to_s(io) : Nil
    io << '(' << from << ", " << to << ", " << cost << ')'
  end

  def inspect(io) : Nil
    io << from << "->" << to << '(' << cost << ')'
  end
end

struct UnweightedEdge2
  property from : Int32, to : Int32

  def initialize(@from, @to)
  end

  def reverse
    UnweightedEdge2.new(to, from)
  end

  def sort
    UnweightedEdge2.new(*{to, from}.minmax)
  end

  def to_s(io) : Nil
    io << '(' << from << ", " << to << ')'
  end

  def inspect(io) : Nil
    io << from << "->" << to
  end
end

abstract class Graph(T)
  getter graph : Array(Array(Edge(T)))

  def initialize(size : Int)
    raise ArgumentError.new("Negative graph size: #{size}") unless size >= 0
    @graph = Array.new(size) { Array(Edge(T)).new }
  end

  def add_edge(from : Int, to : Int, cost : T)
    add_edge(Edge2.new(from, to, cost))
  end

  def add_edge(from_to_cost : {Int32, Int32, T})
    add_edge(Edge2.new(*from_to_cost))
  end

  def add_edges(edges)
    edges.each { |edge| add_edge(edge) }
    self
  end

  delegate size, to: @graph
  delegate :[], to: @graph

  def each_edge : Nil
    (0...size).each do |v|
      graph[v].each do |edge|
        yield Edge2(T).new(v, edge.to, edge.cost)
      end
    end
  end

  def edges
    result = [] of Edge2(T)
    each_edge do |edge|
      result << edge
    end
    result
  end

  def reverse
    result = self.class.new(size)
    each_edge do |edge|
      result.add_edge(edge.reverse)
    end
    result
  end
end

class DirectedGraph(T) < Graph(T)
  def initialize(size : Int)
    super
  end

  def initialize(size : Int, edges : Enumerable(Edge2(T)))
    super(size)
    add_edges(edges)
  end

  def initialize(size : Int, edges : Enumerable({Int32, Int32, T}))
    super(size)
    add_edges(edges)
  end

  def add_edge(edge : Edge2(T))
    raise IndexError.new unless 0 <= edge.from < size && 0 <= edge.to < size
    @graph[edge.from] << Edge.new(edge.to, edge.cost)
    self
  end
end

class UndirectedGraph(T) < Graph(T)
  def initialize(size : Int)
    super
  end

  def initialize(size : Int, edges : Enumerable(Edge2(T)))
    super(size)
    add_edges(edges)
  end

  def initialize(size : Int, edges : Enumerable({Int32, Int32, T}))
    super(size)
    add_edges(edges)
  end

  def add_edge(edge : Edge2(T))
    raise IndexError.new unless 0 <= edge.from < size && 0 <= edge.to < size
    @graph[edge.from] << Edge.new(edge.to, edge.cost)
    @graph[edge.to] << Edge.new(edge.from, edge.cost)
    self
  end
end

abstract class UnweightedGraph
  getter graph : Array(Array(Int32))

  def initialize(size : Int)
    raise ArgumentError.new("Negative graph size: #{size}") unless size >= 0
    @graph = Array.new(size) { Array(Int32).new }
  end

  def add_edge(from : Int, to : Int)
    add_edge(UnweightedEdge2.new(from, to))
  end

  def add_edge(from_to : {Int32, Int32})
    add_edge(*from_to)
  end

  def add_edges(edges)
    edges.each { |edge| add_edge(edge) }
    self
  end

  delegate size, to: @graph
  delegate :[], to: @graph

  def each_edge : Nil
    (0...size).each do |v|
      graph[v].each do |u|
        yield UnweightedEdge2.new(v, u)
      end
    end
  end

  def edges
    result = [] of UnweightedEdge2
    each_edge do |edge|
      result << edge
    end
    result
  end

  def reverse
    result = self.class.new(size)
    each_edge do |edge|
      result.add_edge(edge.reverse)
    end
    result
  end
end

class UnweightedDirectedGraph < UnweightedGraph
  def initialize(size : Int)
    super
  end

  def initialize(size : Int, edges)
    super(size)
    add_edges(edges)
  end

  def add_edge(edge : UnweightedEdge2)
    raise IndexError.new unless 0 <= edge.from < size && 0 <= edge.to < size
    @graph[edge.from] << edge.to
    self
  end

  def to_undirected : self
    result = UnweightedDirectedGraph.new(size)
    each_edge do |edge|
      result.add_edge(edge)
      result.add_edge(edge.reverse)
    end
    result
  end
end

class UnweightedUndirectedGraph < UnweightedGraph
  def initialize(size : Int)
    super
  end

  def initialize(size : Int, edges)
    super(size)
    add_edges(edges)
  end

  def add_edge(edge : UnweightedEdge2)
    raise IndexError.new unless 0 <= edge.from < size && 0 <= edge.to < size
    @graph[edge.from] << edge.to
    @graph[edge.to] << edge.from
    self
  end

  def each_child(vertex : Int, parent, &block) : Nil
    graph[vertex].each do |u|
      yield u if u != parent
    end
  end

  def each_child(vertex : Int, parent)
    graph[vertex].each.select { |u| u != parent }
  end

  def to_undirected : self
    self
  end
end

class Graph(T)
  def bfs01(start : Int, &block)
    raise ArgumentError.new unless 0 <= start < size
    queue = Deque{start}
    dist = Array(Int32?).new(size, nil)
    dist[start] = 0
    while v = queue.shift?
      current_dist = dist[v].not_nil!
      graph[v].each do |edge|
        cost = yield(edge)
        raise ArgumentError.new("Unexpected cost: #{cost}") unless cost == 0 || cost == 1
        next_dist = current_dist + cost
        if (d = dist[edge.to]).nil? || next_dist < d
          dist[edge.to] = next_dist
          if cost == 0
            que.unshift edge.to
          else
            que.push edge.to
          end
        end
      end
    end
    dist
  end

  def bfs01(start : Int)
    bfs01(start, &.cost)
  end

  def bfs01!(start : Int32, &block)
    bfs01(start) { |edge| yield edge }.map(&.not_nil!)
  end

  def bfs01!(start : Int)
    bfs01!(start, &.cost)
  end

  def bfs01_st(start : Int, goal : Int) : Int32?
    raise ArgumentError.new unless 0 <= start < size
    queue = Deque{start}
    dist = Array(Int32?).new(size, nil)
    dist[start] = 0
    while v = queue.shift?
      current_dist = dist[v].not_nil!
      return current_dist if v == goal
      graph[v].each do |edge|
        cost = yield(edge)
        raise ArgumentError.new("Unexpected cost: #{cost}") unless cost == 0 || cost == 1
        next_dist = current_dist + cost
        if (d = dist[edge.to]).nil? || next_dist < d
          dist[edge.to] = next_dist
          if cost == 0
            queue.unshift edge.to
          else
            queue.push edge.to
          end
        end
      end
    end
    nil
  end
end

n, m, k = read_line.split.map(&.to_i)
graph = UndirectedGraph.new n, Array.new(m) {
  u, v, c = read_line.split.map(&.to_i)
  {u - 1, v - 1, c}
}
puts (0..2*10**5).bsearch { |x|
  graph.bfs01_st(0, n - 1) { |edge|
    edge.cost > x ? 1 : 0
  }.not_nil! < k
}