Submission #2797025


Source Code Expand

Copy
INF  = Float::INFINITY
Edge = Struct.new(:from, :to, :cost)
 
class Graph
  attr :edges, :V, :E, :d
  def initialize(v,e)
    @V = v
    @E = e
    @edges = []
    @d = []
  end
 
  def add_graph_edge(u, v, w)
    @edges << Edge.new(u,v,w)
  end
 
  def bellman_ford(source=0)
    @d = Array.new(@V,INF)
    @d[source] = 0
 
    for count in 0...@V
      for i in 0...@edges.length
        v = edges[i].to
        u = edges[i].from
        c = edges[i].cost
 
        if @d[u] != INF and @d[u] + c < @d[v]
          @d[v] = @d[u] + c
          return false if (count >= @V-1 and v==@V-1)
        end
      end
    end
    true
  end
end
 
lines = $stdin.read
array = lines.split("\n")
V,E = array[0].split(" ").map(&:to_i)
graph = Graph.new(V,E)
 
array[1..E].each do |str|
  a,b,c = str.split(" ").map(&:to_i)
  u,v,w = a-1,b-1,-c
  graph.add_graph_edge(u,v,w)
end
 
if graph.bellman_ford()
  puts (-1 * graph.d[V-1])
else
  puts "inf"
end

Submission Info

Submission Time
Task D - Score Attack
User hiroyuking
Language Ruby (2.3.3)
Score 400
Code Size 993 Byte
Status
Exec Time 892 ms
Memory 2172 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt
All 400 / 400 sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_1.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_2.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_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
Case Name Status Exec Time Memory
sample_01.txt 7 ms 1788 KB
sample_02.txt 7 ms 1788 KB
sample_03.txt 7 ms 1788 KB
subtask_1_1.txt 78 ms 1788 KB
subtask_1_10.txt 8 ms 1788 KB
subtask_1_11.txt 82 ms 1788 KB
subtask_1_12.txt 463 ms 2044 KB
subtask_1_13.txt 16 ms 1788 KB
subtask_1_14.txt 475 ms 1916 KB
subtask_1_15.txt 892 ms 2172 KB
subtask_1_16.txt 7 ms 1788 KB
subtask_1_17.txt 11 ms 1788 KB
subtask_1_18.txt 284 ms 2044 KB
subtask_1_19.txt 523 ms 2044 KB
subtask_1_2.txt 379 ms 1916 KB
subtask_1_20.txt 20 ms 1788 KB
subtask_1_21.txt 300 ms 1916 KB
subtask_1_22.txt 744 ms 2172 KB
subtask_1_23.txt 7 ms 1788 KB
subtask_1_24.txt 406 ms 2044 KB
subtask_1_25.txt 131 ms 1916 KB
subtask_1_26.txt 379 ms 1916 KB
subtask_1_27.txt 490 ms 1916 KB
subtask_1_3.txt 228 ms 1916 KB
subtask_1_4.txt 381 ms 1916 KB
subtask_1_5.txt 171 ms 1788 KB
subtask_1_6.txt 487 ms 1916 KB
subtask_1_7.txt 333 ms 1916 KB
subtask_1_8.txt 407 ms 1916 KB
subtask_1_9.txt 7 ms 1788 KB