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

#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

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)
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 2018-07-02 16:09:51+0900 D - Candidates of No Shortest Paths hiroyuking Ruby (2.3.3) 400 2208 Byte AC 847 ms 6140 KB

#### Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt
Case Name Status Exec Time Memory
sample_01.txt 7 ms 1788 KB
sample_02.txt 7 ms 1788 KB