Submission #1030589

---

Source Code Expand

inputs=lambda:map(int,raw_input().split())
n, m = inputs()
es = [inputs() for i in xrange(m)]
es.sort(key=lambda x:x[2])
parent = range(n+1)
def root(x):
    if x == parent[x]:
        return x
    parent[x] = root(parent[x])
    return parent[x]
def unite(x, y):
    px = root(x)
    py = root(y)
    if px < py:
        parent[py] = px
    else:
        parent[px] = py
su = 0
g = [[] for i in xrange(n+1)]
for c, a, b in es:
    if root(a) != root(b):
        unite(a, b)
        su += c
        g[a].append((b, c))
        g[b].append((a, c))

import sys
sys.setrecursionlimit(100000)
dic = {}
def dfs(s, v, prev, cost):
    dic[s,v] = cost
    for e, c in g[v]:
        if prev != e:
            dfs(s, e, v, max(cost, c))
for i in xrange(n):
    dfs(i+1, i+1, -1, 0)
for i in xrange(input()):
    s, t = inputs()
    print su-dic[s,t]

Submission Info

Judge Result