백준/python 1414 불우이웃돕기

# @Date : 2024-09-27 14:13:23
# @Author : ecodev
# @Link : http://ecodev-blog.vercel.app

import sys
input = sys.stdin.readline

############ ---- Input Functions ---- ############


def inp():
    return(int(input()))


def inlt():
    return(list(map(int, input().split())))


def insr():
    s = input()
    return(list(s[:len(s) - 1]))


def invr():
    return(map(int, input().split()))


def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])

    return parent[x]


def union(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)

    if a < b:
        parent[b] = a
    else:
        parent[a] = b


n = inp()
ls = [list(input().rstrip()) for _ in range(n)]
parent = [x for x in range(n + 1)]
edges = []

total = 0

for i in range(n):
    for j in range(n):
        if ls[i][j] != "0":
            if "a" <= ls[i][j] <= "z":
                edges.append((ord(ls[i][j]) - ord("a") + 1, i + 1, j + 1))
                total += ord(ls[i][j]) - ord("a") + 1
            else:
                edges.append((ord(ls[i][j]) - ord("A") + 27, i + 1, j + 1))
                total += ord(ls[i][j]) - ord("A") + 27

edges.sort()

result = 0
for edge in edges:
    cost, a, b = edge

    if find_parent(parent, a) != find_parent(parent, b):
        union(parent, a, b)
        result += cost

for i in range(1, n + 1):
    parent[i] = find_parent(parent, i)

if len(set(parent)) == 2:
    print(total - result)
else:
    print(-1)