CodeForces Beta Round #17 B. Hierarchy

Hierarchy

それぞれの社員についてコストが最小となる直属の上司を探す。2人以上直属の上司が居ない社員が居たら階層を作れない。1人直属の上司が居ない社員が居ればコストの和が答え。全員に直属の上司が居ればコストが最大の社員以外のコストの和。applicationがqualificationの条件を満たしているので、qualificationは不要。

n = input()
raw_input()
m = input()
app = []
for i in range(m):
    app += [[int(x) for x in raw_input().split()]]

cost = [0]*n
for i in range(n):
    t = [a[2] for a in app if a[1]==i+1]
    if len(t) == 0:
        cost[i] = -1
    else:
        cost[i] = min(t)

if cost.count(-1) >= 2:
    print -1
elif cost.count(-1) == 1:
    print sum(cost)+1
else:
    print sum(cost)-max(cost)