Buggy python submission (verdict: Time Limit Exceeded):

import heapq

def prime_method():
    start = graph[0]
    not_went = [True] * n  # n個の点に行ったかという話
    edges = []
    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())
# cities = [(a, b, i) for i, (a, b) in enumerate([tuple(map(int, input().split())) for _ in range(N)])]
cities = []
for i in range(n):
    cities.append(tuple(map(int,input().split()))+tuple([i]))

graph = [[] for i in  range(n)]


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())

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 python submission (verdict: Time Limit Exceeded):

import heapq

def prime_method():
    start = graph[0]
    went = [False] * n  # n個の点に行ったかという話
    edges = []
    for e in start:
        heapq.heappush(edges,e)
    went[0] = True
    cost = 0
    while len(edges) != 0:
        minedge = heapq.heappop(edges)
        if went[minedge[1]]:
            continue
        v = minedge[1]
        gv = graph[v]
        went[v] = True
        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に行ける辺がある

# def prim_heap():
#     used = [True] * n #True:不使用
#     edgelist = []
#     for e in edge[0]:
#         heapq.heappush(edgelist,e)
#     used[0] = False
#     res = 0
#     while len(edgelist) != 0:
#         minedge = heapq.heappop(edgelist)
#         if not used[minedge[1]]:
#             continue
#         v = minedge[1]
#         used[v] = False
#         for e in edge[v]:
#             if used[e[1]]:
#                 heapq.heappush(edgelist,e)
#         res += minedge[0]
#     return res



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




n = int(input())
# cities = [(a, b, i) for i, (a, b) in enumerate([tuple(map(int, input().split())) for _ in range(N)])]
cities = []
for i in range(n):
    cities.append(tuple(map(int,input().split()))+tuple([i]))

graph = [[] for i in  range(n)]


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]])
edge = graph
print(prime_method())

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 python submission (verdict: Time Limit Exceeded):
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():
    start = graph[0]
    went = [False] * n  # n個の点に行ったかという話
    edges = []
    for e in start:
        heapq.heappush(edges,e)
    went[0] = True
    cost = 0
    while len(edges) != 0:
        minedge = heapq.heappop(edges)
        if went[minedge[1]]:
            continue
        v = minedge[1]
        gv = graph[v]
        went[v] = True
        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に行ける辺がある

# def prim_heap():
#     used = [True] * n #True:不使用
#     edgelist = []
#     for e in edge[0]:
#         heapq.heappush(edgelist,e)
#     used[0] = False
#     res = 0
#     while len(edgelist) != 0:
#         minedge = heapq.heappop(edgelist)
#         if not used[minedge[1]]:
#             continue
#         v = minedge[1]
#         used[v] = False
#         for e in edge[v]:
#             if used[e[1]]:
#                 heapq.heappush(edgelist,e)
#         res += minedge[0]
#     return res


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 = [(a, b, i) for i, (a, b) in enumerate([tuple(map(int, input().split())) for _ in range(N)])]
cities = []
for i in range(n):
    cities.append(tuple(map(int,input().split()))+tuple([i]))

graph = [[] for i in  range(n)]


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]])
edge = graph
print(prime_method())

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 python submission (verdict: Time Limit Exceeded):
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():
    start = graph[0]
    n = len(graph)
    went = [False] * n  # n個の点に行ったかという話
    edges = [temp for temp in start ]
    heapq.heapify(edges)
    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 prim_heap():
#     used = [True] * n #True:不使用
#     edgelist = []
#     for e in edge[0]:
#         heapq.heappush(edgelist,e)
#     used[0] = False
#     res = 0
#     while len(edgelist) != 0:
#         minedge = heapq.heappop(edgelist)
#         if not used[minedge[1]]:
#             continue
#         v = minedge[1]
#         used[v] = False
#         for e in edge[v]:
#             if used[e[1]]:
#                 heapq.heappush(edgelist,e)
#         res += minedge[0]
#     return res


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 = [(a, b, i) for i, (a, b) in enumerate([tuple(map(int, input().split())) for _ in range(N)])]
cities = []
for i in range(n):
    cities.append(tuple(map(int,input().split()))+tuple([i]))

graph = [[] for i in  range(n)]


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]])
edge = graph
print(prime_method())

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 python submission (verdict: Time Limit Exceeded):
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():
    start = graph[0]
    n = len(graph)
    went = [False] * n  # n個の点に行ったかという話
    edges = [temp for temp in start ]
    heapq.heapify(edges)
    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 prim_heap():
#     used = [True] * n #True:不使用
#     edgelist = []
#     for e in edge[0]:
#         heapq.heappush(edgelist,e)
#     used[0] = False
#     res = 0
#     while len(edgelist) != 0:
#         minedge = heapq.heappop(edgelist)
#         if not used[minedge[1]]:
#             continue
#         v = minedge[1]
#         used[v] = False
#         for e in edge[v]:
#             if used[e[1]]:
#                 heapq.heappush(edgelist,e)
#         res += minedge[0]
#     return res


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 = [(a, b, i) for i, (a, b) in enumerate([tuple(map(int, input().split())) for _ in range(N)])]
cities = []
for i in range(n):
    cities.append(tuple(map(int,input().split()))+tuple([i]))

graph = [[] for i in  range(n)]


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]])
edge = graph
print(prime_method())

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 python submission (verdict: Time Limit Exceeded):
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 = [temp for temp in start ]
#     heapq.heapify(edges)
#     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 prim_heap():
    used = [True] * n #True:不使用
    edgelist = []
    for e in edge[0]:
        heapq.heappush(edgelist,e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
    return res


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 = [(a, b, i) for i, (a, b) in enumerate([tuple(map(int, input().split())) for _ in range(N)])]
cities = []
for i in range(n):
    cities.append(tuple(map(int,input().split()))+tuple([i]))

graph = [[] for _ in  range(n)]


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([abs(citiesX[i][0] - citiesX[i+1][0]),citiesX[i+1][2]])
    graph[citiesX[i+1][2]].append([abs(citiesX[i][0] - citiesX[i+1][0]),citiesX[i][2]])
    graph[citiesY[i][2]].append([abs(citiesY[i][1] - citiesY[i+1][1]),citiesY[i+1][2]])
    graph[citiesY[i+1][2]].append([abs(citiesY[i][1] - citiesY[i+1][1]),citiesY[i][2]])
edge = graph
print(prim_heap())

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 python submission (verdict: Time Limit Exceeded):
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 = [temp for temp in start ]
#     heapq.heapify(edges)
#     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 prim_heap():
    used = [True] * n #True:不使用
    edgelist = []
    for e in edge[0]:
        heapq.heappush(edgelist,e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
    return res


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 = [(a, b, i) for i, (a, b) in enumerate([tuple(map(int, input().split())) for _ in range(n)])]

graph = [[] for _ in  range(n)]


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([abs(citiesX[i][0] - citiesX[i+1][0]),citiesX[i+1][2]])
    graph[citiesX[i+1][2]].append([abs(citiesX[i][0] - citiesX[i+1][0]),citiesX[i][2]])
    graph[citiesY[i][2]].append([abs(citiesY[i][1] - citiesY[i+1][1]),citiesY[i+1][2]])
    graph[citiesY[i+1][2]].append([abs(citiesY[i][1] - citiesY[i+1][1]),citiesY[i][2]])
edge = graph
print(prim_heap())

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 python submission (verdict: Time Limit Exceeded):
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 = [temp for temp in start ]
#     heapq.heapify(edges)
#     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 prim_heap():
    used = [True] * n #True:不使用
    edgelist = []
    for e in edge[0]:
        heapq.heappush(edgelist,e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
    return res


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 = [(a, b, i) for i, (a, b) in enumerate([tuple(map(int, input().split())) for _ in range(n)])]

graph = [[] for _ in  range(n)]


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([abs(citiesX[i][0] - citiesX[i+1][0]),citiesX[i+1][2]])
    graph[citiesX[i+1][2]].append([abs(citiesX[i][0] - citiesX[i+1][0]),citiesX[i][2]])
    graph[citiesY[i][2]].append([abs(citiesY[i][1] - citiesY[i+1][1]),citiesY[i+1][2]])
    graph[citiesY[i+1][2]].append([abs(citiesY[i][1] - citiesY[i+1][1]),citiesY[i][2]])
edge = graph
print(prim_heap())

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 python submission (verdict: Time Limit Exceeded):
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 = [temp for temp in start ]
#     heapq.heapify(edges)
#     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 prim_heap(edge):
    used = [True] * n #True:不使用
    edgelist = []
    for e in edge[0]:
        heapq.heappush(edgelist,e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
    return res


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 = [(a, b, i) for i, (a, b) in enumerate([tuple(map(int, input().split())) for _ in range(n)])]

graph = [[] for _ in  range(n)]


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([abs(citiesX[i][0] - citiesX[i+1][0]),citiesX[i+1][2]])
    graph[citiesX[i+1][2]].append([abs(citiesX[i][0] - citiesX[i+1][0]),citiesX[i][2]])
    graph[citiesY[i][2]].append([abs(citiesY[i][1] - citiesY[i+1][1]),citiesY[i+1][2]])
    graph[citiesY[i+1][2]].append([abs(citiesY[i][1] - citiesY[i+1][1]),citiesY[i][2]])

print(prim_heap(graph))

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 python submission (verdict: Time Limit Exceeded):
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 = [temp for temp in start ]
    heapq.heapify(edges)
    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 = [(a, b, i) for i, (a, b) in enumerate([tuple(map(int, input().split())) for _ in range(n)])]

graph = [[] for _ in  range(n)]


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([abs(citiesX[i][0] - citiesX[i+1][0]),citiesX[i+1][2]])
    graph[citiesX[i+1][2]].append([abs(citiesX[i][0] - citiesX[i+1][0]),citiesX[i][2]])
    graph[citiesY[i][2]].append([abs(citiesY[i][1] - citiesY[i+1][1]),citiesY[i+1][2]])
    graph[citiesY[i+1][2]].append([abs(citiesY[i][1] - citiesY[i+1][1]),citiesY[i][2]])




print(prime_method(graph))

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 python submission (verdict: Time Limit Exceeded):
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 = [temp for temp in start ]
    heapq.heapify(edges)
    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 = [(a, b, i) for i, (a, b) in enumerate([tuple(map(int, input().split())) for _ in range(n)])]

graph = [[] for _ in  range(n)]


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

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])

s1 = citiesY[0:-1]
s2 = citiesY[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))

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 python submission (verdict: Time Limit Exceeded):
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 = [temp for temp in start ]
    heapq.heapify(edges)
    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 = [(a, b, i) for i, (a, b) in enumerate([tuple(map(int, input().split())) for _ in range(n)])]

graph = [[] for _ in  range(n)]

cities.sort(key = lambda x:x[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[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))

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 python submission (verdict: Time Limit Exceeded):
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])
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[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))

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 python 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))

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 python submission (verdict: Time Limit Exceeded):
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(" "))),i] for i in range(n)]
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[1]
    no2 = city2[1]
    graph[no1].append([abs(city1[0][0] - city2[0][0]),no2])
    graph[no2].append([abs(city1[0][0] - city2[0][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[1]
    no2 = city2[1]
    graph[no1].append([abs(city1[0][1] - city2[0][1]),no2])
    graph[no2].append([abs(city1[0][1] - city2[0][1]),no1])




print(prime_method(graph))

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 python submission (verdict: Time Limit Exceeded):
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]
        for temp in graph[v]:
            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(" "))),i) for i in range(n)]
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[1]
    no2 = city2[1]
    graph[no1].append([abs(city1[0][0] - city2[0][0]),no2])
    graph[no2].append([abs(city1[0][0] - city2[0][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[1]
    no2 = city2[1]
    graph[no1].append([abs(city1[0][1] - city2[0][1]),no2])
    graph[no2].append([abs(city1[0][1] - city2[0][1]),no1])

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]


print(prime_method(graph))

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 python submission (verdict: Time Limit Exceeded):
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]
        for temp in graph[v]:
            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(" "))),i) for i in range(n)]
graph = [[] for _ in  range(n)]

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

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]
    for temp in graph[v]:
        if not went[temp[1]]: #その頂点に行ってなければ
            heapq.heappush(edges,temp)
    went[v] = True
    cost += minedge[0]


print(prime_method(graph))

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 python submission (verdict: Time Limit Exceeded):
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]
        for temp in graph[v]:
            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  = [(input_as_int(),i) for i in range(n)]
graph = [[] for _ in  range(n)]

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


print(prime_method(graph))

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 python submission (verdict: Time Limit Exceeded):
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]
        for temp in graph[v]:
            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  = [(input_as_int(),i) for i in range(n)]
graph = [[] for _ in  range(n)]

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


print(prime_method(graph))

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())