Submission #2781886


Source Code Expand

Copy
# coding: utf-8
#
# :u ノードのインデックス
# :k u の出次数
# :v u に隣接する頂点の番号
# :w 隣接する頂点への重み
#
INF  = Float::INFINITY
Node = Struct.new(:u, :k, :v, :w)

class Graph
  attr :nodes, :dist
  def initialize(n)
    @nodes = Array.new(n){ Node.new }
    @nodes = @nodes.map.with_index do |node,idx|
      node.u = idx
      node
    end
    @dist = Array.new(n).map{Array.new(n, 0)}
  end

  def add_graph_edge(u, v, w)
    #puts "#{u} -> #{v} (#{w})"
    if @nodes[u].v.nil?
      @nodes[u].v = [v]
      @nodes[u].w = {v=>w}
    elsif @nodes[u].v.is_a?(Array)
      @nodes[u].v << v
      @nodes[u].w = {v=>w}.merge(@nodes[u].w)
    else
      @nodes[u].v = [@nodes[u].v, v]
      @nodes[u].w = {v=>w}.merge(@nodes[u].w)
    end
    @nodes[u].k = if @nodes[u].v.is_a?(Array)
                    @nodes[u].v.length
                  else
                    1
                  end
  end

  def warshall_floyd()
    # initialize
    for i in 0...@nodes.length
      for j in 0...@nodes.length
        @dist[i][j] = if not @nodes[i].w.nil? and @nodes[i].w.has_key?(j)
                        @nodes[i].w[j]
                      else
                        INF
                      end
      end
      @dist[i][i] = 0
    end

    # calc
    for k in 0...@nodes.length
      for i in 0...@nodes.length
        for j in 0...@nodes.length
          if @dist[i][k] != INF and @dist[k][j] != INF
            @dist[i][j] = [@dist[i][j], @dist[i][k] + @dist[k][j]].min
          end
        end
      end
    end
  end

  def has_negative_cycle?()
    ans = false
    for v in 0...@nodes.length
      ans = true if @dist[v][v] < 0
    end
    ans
  end
end

lines = $stdin.read
array = lines.split("\n")

N,M = array[0].split(" ").map(&:to_i)
graph = Graph.new(N)

array[1..M].each do |s|
  s,t,d = s.split(" ").map(&:to_i)
  graph.add_graph_edge(s-1,t-1,d)
  graph.add_graph_edge(t-1,s-1,d)
end

# execute WarshallFloyd !
graph.warshall_floyd()

ans = array[1..M].count do |s|
  s,t,d = s.split(" ").map(&:to_i)
  s,t = s-1,t-1
  graph.dist[s][t] != d
end

puts ans

Submission Info

Submission Time
Task D - Candidates of No Shortest Paths
User hiroyuking
Language Ruby (2.3.3)
Score 400
Code Size 2208 Byte
Status
Exec Time 847 ms
Memory 6140 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt
All 400 / 400 sample_01.txt, sample_02.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt
Case Name Status Exec Time Memory
sample_01.txt 7 ms 1788 KB
sample_02.txt 7 ms 1788 KB
subtask_1_01.txt 10 ms 1788 KB
subtask_1_02.txt 70 ms 1916 KB
subtask_1_03.txt 273 ms 1916 KB
subtask_1_04.txt 395 ms 1916 KB
subtask_1_05.txt 747 ms 2940 KB
subtask_1_06.txt 34 ms 1916 KB
subtask_1_07.txt 101 ms 1916 KB
subtask_1_08.txt 378 ms 1916 KB
subtask_1_09.txt 416 ms 1916 KB
subtask_1_10.txt 427 ms 1916 KB
subtask_1_11.txt 18 ms 1916 KB
subtask_1_12.txt 128 ms 2044 KB
subtask_1_13.txt 603 ms 2300 KB
subtask_1_14.txt 294 ms 2684 KB
subtask_1_15.txt 783 ms 2300 KB
subtask_1_16.txt 10 ms 1916 KB
subtask_1_17.txt 22 ms 2300 KB
subtask_1_18.txt 49 ms 3580 KB
subtask_1_19.txt 99 ms 5500 KB
subtask_1_20.txt 23 ms 2300 KB
subtask_1_21.txt 15 ms 1916 KB
subtask_1_22.txt 128 ms 1916 KB
subtask_1_23.txt 59 ms 3196 KB
subtask_1_24.txt 652 ms 3708 KB
subtask_1_25.txt 179 ms 5116 KB
subtask_1_26.txt 353 ms 4860 KB
subtask_1_27.txt 811 ms 4220 KB
subtask_1_28.txt 847 ms 6140 KB