Submission #2870245
Source Code Expand
# coding: utf-8 # # ---------------------- # WarshallFloyd # ---------------------- # :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...V ans = true if @dist[v][v] < 0 end ans end end lines = $stdin.read array = lines.split("\n") N,M,R = array[0].split(" ").map(&:to_i) graph = Graph.new(N) rarr = array[1].split(" ").map(&:to_i).map{|idx| idx-1} array[2..M+1].each do |s| s,t,d = s.split(" ").map(&:to_i) s,t=s-1,t-1 graph.add_graph_edge(s,t,d) graph.add_graph_edge(t,s,d) end # execute WarshallFloyd ! graph.warshall_floyd() ans = INF rarr.permutation(R).each do |picked| s = picked.each_cons(2).map do |arr| graph.dist[arr.first][arr.last] end.inject(&:+) ans = [s,ans].min end puts ans
Submission Info
Submission Time | |
---|---|
Task | D - joisino's travel |
User | hiroyuking |
Language | Ruby (2.3.3) |
Score | 0 |
Code Size | 2390 Byte |
Status | TLE |
Exec Time | 2113 ms |
Memory | 83324 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 400 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
All | 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, sample_01.txt, sample_02.txt, sample_03.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01.txt | TLE | 2113 ms | 80508 KB |
02.txt | TLE | 2107 ms | 2684 KB |
03.txt | TLE | 2102 ms | 2684 KB |
04.txt | TLE | 2107 ms | 6908 KB |
05.txt | TLE | 2108 ms | 8956 KB |
06.txt | TLE | 2113 ms | 83324 KB |
07.txt | TLE | 2113 ms | 81532 KB |
08.txt | AC | 1099 ms | 2684 KB |
sample_01.txt | AC | 7 ms | 1788 KB |
sample_02.txt | AC | 7 ms | 1788 KB |
sample_03.txt | AC | 8 ms | 1788 KB |