Submission #1725365
Source Code Expand
INF = 999999999 Node = Struct.new(:u, :d, :c, :p) class Graph attr :nodes, :mat, :u_start def initialize(n, matrix, u_start_with = 1) @nodes = Array.new(n){ Node.new } @nodes.each_with_index{|node,idx| node.u = idx+u_start_with} @u_start = u_start_with @mat = matrix.dup end def edge_exists?(row, col) #printf " edge_exists?(#{row}, #{col}) => " row -= @u_start col -= @u_start result = if @mat[row][col] != -1 # or @mat[col][row] != -1 true else false end #puts "#{result} => cost: #{@mat[row][col]}" result end def gen_uniq_edges() edges = [] @nodes.each_with_index do |node,i| mat[i].map.with_index.select do |w,idx| w != -1 end.each do |w,idx| edge = [node.u, idx+@u_start] edges << edge end end edges.uniq end def dot_before_dijkstra() puts "graph beforeDijkstra {" gen_uniq_edges.each do |e| puts " \"#{e.first}\" -- \"#{e.last}\" [label=#{mat[e.first-@u_start][e.last-@u_start]}]" end puts "}" end def dot_after_dijkstra(start = 1) # start dijkstra dijkstra(start) # then, generate dot puts "digraph afterDijkstra {" gen_uniq_edges.each do |e| no = mat[e.first-1.to_i].detect {|m| m != -1 and (m == e.last-1 or m == e.first-1) } if no.nil? puts " \"#{e.first}\" -- \"#{e.last}\" [label=\"w=#{mat[e.first-1][e.last-1]}\"]" else puts " \"#{e.first}\" -- \"#{e.last}\" [label=\"w=#{mat[e.first-1][e.last-1]} (#{no})\", penwidth=3]" end end puts "}" end def dijkstra(start = 1) @nodes = @nodes.each do |node| node.d = INF node.p = nil node.c = :white end start = (start-@u_start).to_i @nodes[start].d = 0 @nodes[start].p = -1 next_u = nil while true mincost = INF @nodes.each do |node| if node.c != :black and node.d < mincost #puts "node.d = #{node.d}" mincost = node.d next_u = node.u end end #puts "mincost = #{mincost}, next_u = #{next_u}" break if mincost == INF @nodes[next_u].c = :black @nodes = @nodes.map.with_index do |node, v| if node.c != :black and edge_exists?(next_u, v) and @nodes[next_u].d + mat[next_u][v] < node.d node.d = @nodes[next_u].d + mat[next_u][v] node.p = next_u node.c = :gray node else node end end end end end lines = $stdin.read array = lines.split("\n") N,M = array[0].split(" ").map(&:to_i) mat = Array.new(N).map{Array.new(N, -1)} for i in 1..M u,v,w = array[i].split(" ").map(&:to_i) mat[u-1][v-1] = w mat[v-1][u-1] = w end # 0-indexed graph = Graph.new(N, mat, 0) # start-with 0 #graph.dot_before_dijkstra() min_t = graph.nodes.map do |n| graph.dijkstra(n.u) graph.nodes.max_by{|node| node.d}.d end.to_a.min puts min_t
Submission Info
Submission Time | |
---|---|
Task | D - バスと避けられない運命 |
User | hiroyuking |
Language | Ruby (2.3.3) |
Score | 0 |
Code Size | 3113 Byte |
Status | TLE |
Exec Time | 5262 ms |
Memory | 52632 KB |
Judge Result
Set Name | All | ||||
---|---|---|---|---|---|
Score / Max Score | 0 / 100 | ||||
Status |
|
Set Name | Test Cases |
---|---|
All | sample_01.txt, sample_02.txt, sample_03.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt, test_36.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 7 ms | 1788 KB |
sample_02.txt | AC | 7 ms | 1788 KB |
sample_03.txt | AC | 7 ms | 1788 KB |
test_01.txt | AC | 7 ms | 1788 KB |
test_02.txt | TLE | 5260 ms | 11756 KB |
test_03.txt | TLE | 5261 ms | 33916 KB |
test_04.txt | AC | 2794 ms | 8752 KB |
test_05.txt | AC | 3128 ms | 14332 KB |
test_06.txt | AC | 278 ms | 3836 KB |
test_07.txt | TLE | 5262 ms | 52632 KB |
test_08.txt | AC | 20 ms | 2044 KB |
test_09.txt | AC | 2090 ms | 6572 KB |
test_10.txt | AC | 226 ms | 3836 KB |
test_11.txt | AC | 263 ms | 3836 KB |
test_12.txt | AC | 4360 ms | 7968 KB |
test_13.txt | AC | 288 ms | 3836 KB |
test_14.txt | AC | 450 ms | 3836 KB |
test_15.txt | TLE | 5262 ms | 36604 KB |
test_16.txt | AC | 502 ms | 3708 KB |
test_17.txt | AC | 2392 ms | 13692 KB |
test_18.txt | AC | 3869 ms | 5672 KB |
test_19.txt | AC | 558 ms | 3708 KB |
test_20.txt | AC | 468 ms | 3836 KB |
test_21.txt | AC | 8 ms | 1788 KB |
test_22.txt | AC | 1388 ms | 4792 KB |
test_23.txt | AC | 13 ms | 1916 KB |
test_24.txt | TLE | 5260 ms | 11892 KB |
test_25.txt | TLE | 5260 ms | 13800 KB |
test_26.txt | AC | 1762 ms | 6652 KB |
test_27.txt | AC | 2367 ms | 8572 KB |
test_28.txt | TLE | 5260 ms | 11904 KB |
test_29.txt | TLE | 5260 ms | 11812 KB |
test_30.txt | AC | 341 ms | 2940 KB |
test_31.txt | AC | 31 ms | 2300 KB |
test_32.txt | TLE | 5260 ms | 11928 KB |
test_33.txt | TLE | 5260 ms | 13748 KB |
test_34.txt | AC | 117 ms | 2556 KB |
test_35.txt | AC | 1388 ms | 3452 KB |
test_36.txt | TLE | 5260 ms | 13740 KB |