Problem p03684 (python)

Fixed submission:

import heapq

def prime_method():
    not_went = [True] * n  # n個の点に行ったかという話
    edges = []
    start = graph[0]
    for e in start:
        heapq.heappush(edges,e)
    not_went[0] = False
    cost = 0
    while len(edges) != 0:
        minedge = heapq.heappop(edges)
        if not not_went[minedge[1]]:
            continue
        v = minedge[1]
        gv = graph[v]
        not_went[v] = False
        for temp in gv:
            if not_went[temp[1]]:  # その頂点に行ってなければ
                heapq.heappush(edges, temp)
        cost += minedge[0]
    return cost
    # a[1] = [[2,3],[5,11]] → 点1からコスト2で頂点3に行ける辺、点1からコスト5で頂点11に行ける辺がある


n = int(input())
graph = [[] for i in  range(n)]
cities = []
for i in range(n):
    cities.append(tuple(map(int,input().split()))+tuple([i]))


citiesX=sorted(cities,key=lambda x:x[0])
citiesY=sorted(cities,key=lambda x:x[1])

for i in range(n-1):
    graph[citiesX[i][2]].append(((citiesX[i+1][0] - citiesX[i][0]),citiesX[i+1][2]))
    graph[citiesX[i+1][2]].append(((citiesX[i+1][0] - citiesX[i][0]),citiesX[i][2]))
    graph[citiesY[i][2]].append(((citiesY[i+1][1] - citiesY[i][1]),citiesY[i+1][2]))
    graph[citiesY[i+1][2]].append(((citiesY[i+1][1] - citiesY[i][1]),citiesY[i][2]))
print(prime_method())

Buggy submission (verdict: Runtime Error):
import heapq
import collections
import heapq
def input_as_int():
    return list(map(int,input().split()))


def get_comb(n):  # n C n まで

    fac = get_fact(n)
    com  = [["error" for _ in range(n+1)] for _ in range (n + 1)]
    for i in range(n + 1):
        for j in range(i + 1):
            if  i >= j:
                com[i][j] = fac[i] // (fac[i-j] * fac[j])

    return com


def get_fact(n):
    temp = 1
    fac = [1]
    for i in range(1, n + 1):
        temp *= i
        fac.append(temp)
    return fac

def prime_method(graph):
    start = graph[0]
    n = len(graph)
    went = [False] * n  # n個の点に行ったかという話
    edges = []
    for temp in start:
        heapq.heappush(edges, temp)
    went[0] = True
    cost = 0
    while len(edges) != 0:
        minedge = heapq.heappop(edges)
        if went[minedge[1]]:
            continue
        v = minedge[1]
        gv = graph[v]
        for temp in gv:
            if not went[temp[1]]:  # その頂点に行ってなければ
                heapq.heappush(edges, temp)
        went[v] = True
        cost += minedge[0]
    return cost
    # a[1] = [[2,3],[5,11]] → 点1からコスト2で頂点3に行ける辺、点1からコスト5で頂点11に行ける辺がある

def get_graph():
    n = input()
    graph = [input_as_int() for _ in range(n)]


    # a[1] = [[2,3],[5,11]] → 点1からコスト2で頂点3に行ける辺、点1からコスト5で頂点11に行ける辺がある


n = int(input())
cities  = [list(map(int,input().split(" "))) for i in range(n)]
for i in range(n):
    cities[i].append(i)
graph = [[] for _ in  range(n)]

cities.sort(key = lambda x:x[0][0])
citiesX = cities
s1,s2 = citiesX[0:-1],citiesX[1:]
for city1,city2 in zip(s1,s2):
    no1 = city1[2]
    no2 = city2[2]
    graph[no1].append([abs(city1[0] - city2[0]),no2])
    graph[no2].append([abs(city1[0] - city2[0]),no1])
cities.sort(key =lambda x:x[0][1])
s1 = cities[0:-1]
s2 = cities[1:]
for city1,city2 in zip(s1,s2):
    no1 = city1[2]
    no2 = city2[2]
    graph[no1].append([abs(city1[1] - city2[1]),no2])
    graph[no2].append([abs(city1[1] - city2[1]),no1])




print(prime_method(graph))