Submission #3780399

---

Source Code Expand

N, M = gets.split.map(&:to_i)
es = []
edges = Array.new(N){[]}
M.times do |i|
    a, b, c = gets.split.map(&:to_i)
    es.push([a-1, b-1, c])
    edges[a-1].push([b-1, c, i])
    edges[b-1].push([a-1, c, i])
end

INF = 10**18
dist = Array.new(N, INF)
used = []
prev = []
dist[0] = 0
loop do
    v = -1
    N.times do |u|
        if !used[u] && (v == -1 || dist[u] < dist[v])
            v = u
        end
    end
    break if v == -1
    used[v] = true
    edges[v].each do |u, c, e|
        if dist[u] > dist[v] + c
            dist[u] = dist[v] + c
            prev[u] = e
        end
    end
end

tree = []
(1...N).each do |i|
    tree[prev[i]] = true if prev[i]
end

ans = INF
M.times do |e|
    next if tree[e]
    result = dist[es[e][0]] + dist[es[e][1]] + es[e][2]
    ans = result if ans > result
end

puts ans==INF ? -1 : ans

Submission Info

Judge Result