Problem:


Score : 500 points

Problem Statement

There are N towns on a plane. The i-th town is located at the coordinates (x_i,y_i). There may be more than one town at the same coordinates.

You can build a road between two towns at coordinates (a,b) and (c,d) for a cost of min(|a-c|,|b-d|) yen (the currency of Japan). It is not possible to build other types of roads.

Your objective is to build roads so that it will be possible to travel between every pair of towns by traversing roads. At least how much money is necessary to achieve this?

Constraints

2 ≤ N ≤ 10^5

0 ≤ x_i,y_i ≤ 10^9

All input values are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
x_2 y_2
:
x_N y_N

Output

Print the minimum necessary amount of money in order to build roads so that it will be possible to travel between every pair of towns by traversing roads.

Sample Input 1

3
1 5
3 9
7 8

Sample Output 1

3

Build a road between Towns 1 and 2, and another between Towns 2 and 3. The total cost is 2+1=3 yen.

Sample Input 2

6
8 3
4 9
12 19
18 1
13 5
7 6

Sample Output 2

8



Sample input:
3
1 5
3 9
7 8


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
n = int(input())
x =[]
y =[]
info = [list(map(int,input().split())) for i in range(n)]
for i in range(n):
  x.append([i,info[i][0]])
  y.append([i,info[i][1]])

x = sorted(x,key=itemgetter(1))
y = sorted(y,key=itemgetter(1))
tree = []
#for i in range(n):
#  if i==0:
#    tree[x[i][0]].append([x[i+1][0],abs(x[i][1]-x[i+1][1])])
#    tree[y[i][0]].append([y[i+1][0],abs(y[i][1]-y[i+1][1])])
#  elif i==n-1:
#    tree[x[i][0]].append([x[i-1][0],abs(x[i][1]-x[i-1][1])])
#    tree[y[i][0]].append([y[i-1][0],abs(y[i][1]-y[i-1][1])])
#  else:
#    tree[x[i][0]].append([x[i+1][0],abs(x[i][1]-x[i+1][1])])
#    tree[x[i][0]].append([x[i-1][0],abs(x[i][1]-x[i-1][1])])
#    tree[y[i][0]].append([y[i+1][0],abs(y[i][1]-y[i+1][1])])
#    tree[y[i][0]].append([y[i-1][0],abs(y[i][1]-y[i-1][1])])
    
for i in range(n-1):
    tree.append([x[i][0],x[i+1][0],abs(x[i][1]-x[i+1][1])])
    tree.append([y[i][0],y[i+1][0],abs(y[i][1]-y[i+1][1])])

#UnionFindクラス
class UnionFind(object):

  def __init__(self, n=1):
    self.par = [i for i in range(n)]
    self.rank = [0 for _ in range(n)]

  def find(self, x):
  
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
  
  # xとyの根を結合させる
  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x != y:
      if self.rank[x] < self.rank[y]:
        x, y = y, x
      if self.rank[x] == self.rank[y]:
        self.rank[x] += 1
      self.par[y] = x
  
  # x,yの根が同じかどうかを返す（根が同じ:True、根が異なる:False）
  def is_same(self, x, y):
    return self.find(x) == self.find(y)

uf = UnionFind(len(tree))
tree = sorted(tree,key=itemgetter(2))
ans = 0

for i in range(len(tree)):
  if not uf.is_same(tree[i][0],tree[i][1]):
    uf.union(tree[i][0],tree[i][1])
    ans +=tree[i][2]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
from heapq import heappush, heappop, heapify

n=int(input())
a,b=map(int,input().split())
G=[(a,b)]
que = []
for i in range(n-1):
    x,y=map(int,input().split())
    G.append((x,y))
    heappush(que,(min(abs(a-x),abs(b-y)),i+1))
used = [0 for i in range(n)]
used[0] = 1

ans = 0
while que:
    cv, v = heappop(que)
    if used[v]:
        continue
    used[v] = 1
    ans += cv
    for i in range(n):
        if used[i]:
            continue
        heappush(que, (min(abs(G[i][0]-G[v][0]),abs(G[i][1]-G[v][1])), i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
xys = [list(map(int, input().split())) + [i] for i in range(n)]
edges = []
xys.sort()
for i in range(n - 1):
    x1, y1, index1 = xys[i]
    x2, y2, index2 = xys[i + 1]
    edges.append((x2 - x1, index1, index2))

xys.sort(key=lambda x:x[1])
for i in range(n - 1):
    x1, y1, index1 = xys[i]
    x2, y2, index2 = xys[i + 1]
    edges.append((y2 - y1, index1, index2))

parent = [i for i in range(n)]
def find(x):
    if x == parent[x]:return x
    parent[x] = find(parent[x])
    return parent[x]

edges.sort()
ans = 0
for cost, index1, index2 in edges:
    p1, p2 = find(index1), find(index2)
    if p1 != p2:
        parent[p1] = p2
        ans += cost
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from  heapq import heappush, heappop, heapify

N=int(input())

par=[ i for i in range(N) ]

def root(x):
	if par[x]==x:
		return x
	else:
		par[x]=root( par[x] )
		return par[x]

def same(x,y):
	return root(x)==root(y)

def unite(x,y):
	x=root(x)
	y=root(y)
	if x==y: return
	par[x]=y



X=[]
Y=[]
for i in range(N):
	x,y=map(int, sys.stdin.readline().split()) 
	X.append( (x,i) )
	Y.append( (y,i) )

X.sort(key=lambda x: x[0])
Y.sort(key=lambda x: x[0])

hq=[]

prev_x=None
prev_i=None
for x,i in X:
	if prev_x is not None:	
		heappush( hq, ( x-prev_x, i, prev_i) )
	prev_x=x
	prev_i=i

prev_x=None
prev_i=None
for x,i in Y:
	if prev_x is not None:	
		heappush( hq, ( x-prev_x, i, prev_i) )
	prev_x=x
	prev_i=i


ans=0
while hq:
	d,a,b=heappop(hq)
	if not same(a,b):
		ans+=d
		unite(a,b)
		
print (ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from  heapq import heappush, heappop, heapify

N=input()

par=[ i for i in range(N) ]

def root(x):
	if par[x]==x:
		return x
	else:
		par[x]=root( par[x] )
		return par[x]

def same(x,y):
	return root(x)==root(y)

def unite(x,y):
	x=root(x)
	y=root(y)
	if x==y: return
	par[x]=y



X=[]
Y=[]
for i in range(N):
	x,y=map(int, sys.stdin.readline().split()) 
	X.append( (x,i) )
	Y.append( (y,i) )

X.sort(key=lambda x: x[0])
Y.sort(key=lambda x: x[0])

hq=[]

prev_x=None
prev_i=None
for x,i in X:
	if prev_x is not None:	
		heappush( hq, ( x-prev_x, i, prev_i) )
	prev_x=x
	prev_i=i

prev_x=None
prev_i=None
for x,i in Y:
	if prev_x is not None:	
		heappush( hq, ( x-prev_x, i, prev_i) )
	prev_x=x
	prev_i=i


ans=0
while hq:
	d,a,b=heappop(hq)
	if not same(a,b):
		ans+=d
		unite(a,b)
		
print ans

Submission status: Time Limit Exceeded

Solution code:
import itertools

def find(table, x):
    while table[x] != x:
        x = table[x]
    return x

def union(table, x1, x2):
    p1 = find(table, x1)
    p2 = find(table, x2)
    table[p2] = p1

n = int(input())
points = [tuple(map(int, input().split())) for _ in range(n)]

edges = []
for j in (0, 1):
    cities1, cities2 = itertools.tee(sorted(range(n), key=lambda city: points[city][j]), 2)
    for city1, city2 in zip(cities1, itertools.islice(cities2, 1, None)):
        (x1, y1), (x2, y2) = points[city1], points[city2]
        cost = min(abs(x1 - x2), abs(y1 - y2))
        edges.append((cost, city1, city2))
edges.sort() # key=lambda cost, city1, city2: cost

table = list(range(n))
answer = 0
for cost, city1, city2 in edges:
    parent1, parent2 = find(table, city1), find(table, city2)
    if parent1 != parent2:
        answer += cost
        union(table, city1, city2)

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import array
import collections
import heapq

AdjacentVertex = collections.namedtuple("AdjacentVertex", "vertex cost")
INF = 2 ** 31 - 1
NO_VERTEX = -1


# Prim法で頂点0からの最小全域木を求める
def compute_mst_prim(max_v, adj_list):
    # pred[u]は頂点uの「ひとつ前」の頂点を表す
    pred = collections.defaultdict(lambda: NO_VERTEX)
    # uとpred[u]を結ぶ辺の重みがkey[u]に入る
    key = collections.defaultdict(lambda: INF)
    key[0] = 0
    # 二分ヒープを優先度付きキューとして用いる
    pq = [(key[v], v) for v in range(max_v)]
    heapq.heapify(pq)
    # 優先度付きキューに頂点が入っているかを示す配列
    in_pq = array.array("B", (True for _ in range(max_v)))
    while pq:
        _, u = heapq.heappop(pq)
        in_pq[u] = False
        for v, v_cost in adj_list[u]:
            if in_pq[v]:
                weight = v_cost
                if weight < key[v]:
                    pred[v] = u
                    key[v] = weight
                    heapq.heappush(pq, (weight, v))
                    in_pq[v] = True
    return (pred, key)


def main():
    n = int(input())
    z = []
    for i in range(n):  # h:高さ
        z.append([int(m) for m in input().split()] + [i])

    zx = sorted(z, key=lambda x: (x[0]))
    zy = sorted(z, key=lambda x: (x[1]))

    # 最小木問題をプリム法で解く

    # 点群を発生
    p = [[zx[i][2], zx[i + 1][2], min(abs(zx[i][0] - zx[i + 1][0]), abs(zx[i][1] - zx[i + 1][1]))] for i in range(n - 1)]
    p += [[zy[i][2], zy[i + 1][2], min(abs(zy[i][0] - zy[i + 1][0]), abs(zy[i][1] - zy[i + 1][1]))] for i in range(n - 1)]

    max_v, max_e = n, len(p)
    adjacency_list = collections.defaultdict(set)
    for i in range(max_e):
        s, t, w = p[i][0], p[i][1], p[i][2]
        adjacency_list[s].add(AdjacentVertex(t, w))
        adjacency_list[t].add(AdjacentVertex(s, w))
    (_, key) = compute_mst_prim(max_v, adjacency_list)
    print(sum(key.values()))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
Cx = [[0, 0] for i in range(N)]
Cy = [[0, 0] for i in range(N)]
for i in range(N):
  x, y = map(int, input().split())
  Cx[i] = [x, i]
  Cy[i] = [y, i]
Cx.sort()
Cy.sort()
Qx = sorted([[Cx[i + 1][0] - Cx[i][0], Cx[i][1], Cx[i + 1][1]] for i in range(N - 1)])
Qy = sorted([[Cy[i + 1][0] - Cy[i][0], Cy[i][1], Cy[i + 1][1]] for i in range(N - 1)])
R = [i for i in range(N)]
def root(n):
  if R[n] == n:
    return n
  else:
    R[n] = root(R[n])
    return R[n]
cnt = 0
cost = 0
x = 0
y = 0
while cnt < N - 1:
  if Qx[x][0] <= Qy[y][0]:
    q = Qx[x]
    x += 1
  else:
    q = Qy[y]
    y += 1
  r1 = root(q[1])
  r2 = root(q[2])
  if r1 != r2:
    R[r2] = q[1]
    cost += q[0]
    cnt += 1
print(cost)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
Cx = [[] for i in range(N)]
Cy = [[] for i in range(N)]
for i in range(N):
  x, y = map(int, input().split())
  Cx[i] = [x, i]
  Cy[i] = [y, i]
Cx.sort()
Cy.sort()
Qx = [[Cx[i + 1][0] - Cx[i][0], Cx[i][1], Cx[i + 1][1]] for i in range(N - 1)]
Qx.sort()
Qy = [[Cy[i + 1][0] - Cy[i][0], Cy[i][1], Cy[i + 1][1]] for i in range(N - 1)]
Qy.sort()
R = [i for i in range(N)]
def root(n):
  if R[n] == n:
    return n
  else:
    R[n] = root(R[n])
    return R[n]
cnt = 0
cost = 0
while cnt < N - 1:
  if Qx[0][0] <= Qy[0][0]:
    q = Qx[0]
    Qx = Qx[1:]
  else:
    q = Qy[0]
    Qy = Qy[1:]
  r1 = root(q[1])
  r2 = root(q[2])
  if r1 != r2:
    R[r2] = q[1]
    cost += q[0]
    cnt += 1
print(cost)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
Cx = [[] for i in range(N)]
Cy = [[] for i in range(N)]
for i in range(N):
  x, y = map(int, input().split())
  Cx[i] = [x, i]
  Cy[i] = [y, i]
Cx.sort()
Cy.sort()
Qx = [[Cx[i + 1][0] - Cx[i][0], Cx[i][1], Cx[i + 1][1]] for i in range(N - 1)]
Qx.sort()
Qy = [[Cy[i + 1][0] - Cy[i][0], Cy[i][1], Cy[i + 1][1]] for i in range(N - 1)]
Qy.sort()
R = [i for i in range(N)]
def root(n):
  if R[n] == n:
    return n
  else:
    R[n] = root(R[n])
    return R[n]
cnt = 0
cost = 0
x = 0
y = 0
while cnt < N - 1:
  if Qx[x][0] <= Qy[y][0]:
    q = Qx[x]
    x += 1
  else:
    q = Qy[y]
    y += 1
  if root(q[1]) != root(q[2]):
    R[R[q[2]]] = q[1]
    cost += q[0]
    cnt += 1
print(cost)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
C = [[] for i in range(N)]
for i in range(N):
  x, y = map(int, input().split())
  C[i] = [x, y, i]
Cx = sorted(C, key=lambda c: c[0])
Cy = sorted(C, key=lambda c: c[1])
Qx = sorted([[Cx[i + 1][0] - Cx[i][0], Cx[i][2], Cx[i + 1][2]] for i in range(N - 1)])
Qy = sorted([[Cy[i + 1][1] - Cy[i][1], Cy[i][2], Cy[i + 1][2]] for i in range(N - 1)])
R = [i for i in range(N)]
def root(n):
  if R[n] == n:
    return n
  else:
    R[n] = root(R[n])
    return R[n]
cnt = 0
cost = 0
x = 0
y = 0
while cnt < N - 1:
  if Qx[x][0] <= Qy[y][0]:
    q = Qx[x]
    x += 1
  else:
    q = Qy[y]
    y += 1
  if root(q[1]) != root(q[2]):
    R[R[q[2]]] = q[1]
    cost += q[0]
    cnt += 1
print(cost)

Submission status: Time Limit Exceeded

Solution code:
import heapq
N = int(input())
C = [[] for i in range(N)]
for i in range(N):
  x, y = map(int, input().split())
  C[i] = [x, y, i]
Cx = sorted(C, key=lambda c: c[0])
Cy = sorted(C, key=lambda c: c[1])
Q = []
for i in range(N - 1):
  heapq.heappush(Q, [Cx[i + 1][0] - Cx[i][0], Cx[i][2], Cx[i + 1][2]])
  heapq.heappush(Q, [Cy[i + 1][1] - Cy[i][1], Cy[i][2], Cy[i + 1][2]])
R = [i for i in range(N)]
def root(n):
  if R[n] == n:
    return n
  else:
    R[n] = root(R[n])
    return R[n]
cnt = 0
cost = 0
while cnt < N - 1:
  q = heapq.heappop(Q)
  if root(q[1]) != root(q[2]):
    R[q[2]] = q[1]
    cost += q[0]
    cnt += 1
print(cost)

Submission status: Time Limit Exceeded

Solution code:
import sys
fin = sys.stdin.readline
from heapq import heappop, heappush


class UnionFind(object):
    def __init__(self, N):
        self.__root = list(range(N))
    

    def root(self, x):
        if self.__root[x] == x:
            return x
        else:
            # root abbreviation
            self.__root[x] = self.root(self.__root[x])
            return self.__root[x]

    
    def same(self, x, y):
        return self.root(x) == self.root(y)


    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if (x == y):
            return
        self.__root[y] = x
        return


# assuming that the vertices are 0, 1, ..., N - 1
# if V^2 >> E, use a hashmap representation of w
# time complexity: O(ElgE)
# space complexity: O(E)
def prim(adj, w):
    num_vertices = len(adj)
    # initialize
    min_cost = [float('inf')] * num_vertices
    min_cost[0] = 0
    used = [False] * num_vertices
    priority_queue = [(0, 0)]
    total_cost = 0

    while priority_queue:
        cost, vertex = heappop(priority_queue)
        if cost > min_cost[vertex] or used[vertex]:
            continue
        used[vertex] = True
        total_cost += cost

        for neighbor in adj[vertex]:
            cost_v_to_n = w[(vertex, neighbor)]
            if min_cost[neighbor] > cost_v_to_n:
                min_cost[neighbor] = cost_v_to_n
                heappush(priority_queue, (cost_v_to_n, neighbor))

    return total_cost


# input should be [(s1, t1, cost1), (s2, t2, cost2), ...]
# time complexity: O(ElgV)
# space complexity: O(E)
def kruskal(edges_with_cost, num_vertices):
    # num_edges = len(edges_with_cost)
    edges_with_cost.sort(key=lambda x: x[-1])
    uf = UnionFind(num_vertices)
    total_cost = 0
    for source, target, cost in edges_with_cost:
        if not uf.same(source, target):
            uf.unite(source, target)
            total_cost += cost
    
    return total_cost


N = int(fin())
coords = [[int(elem) for elem in fin().split()] + [i] for i in range(N)]

edges_with_cost = []
# sort coords in increasing order of x
coords.sort(key=lambda x: x[0])
for i, (x, _, vertex) in enumerate(coords[:-1]):
    next_x, _, next_vertex = coords[i + 1]
    weight = next_x - x
    edges_with_cost.append((vertex, next_vertex, weight))
    edges_with_cost.append((next_vertex, vertex, weight))


# sort coods in increasing order of y
coords.sort(key=lambda x: x[1])
for i, (_, y, vertex) in enumerate(coords[:-1]):
    _, next_y, next_vertex = coords[i + 1]
    weight = next_y - y
    edges_with_cost.append((vertex, next_vertex, weight))
    edges_with_cost.append((next_vertex, vertex, weight))

print(kruskal(edges_with_cost, N))

# adj = [set() for _ in range(N)]
# w = {}
# # sort coords in increasing order of x
# coords.sort(key=lambda x: x[0])
# for i, (x, _, vertex) in enumerate(coords[:-1]):
#     next_x, _, next_vertex = coords[i + 1]
#     adj[vertex].add(next_vertex)
#     adj[next_vertex].add(vertex)
#     weight = next_x - x
#     if (vertex, next_vertex) not in w or w[(vertex, next_vertex)] > weight:
#         w[(vertex, next_vertex)] = weight
#     if (next_vertex, vertex) not in w or w[(next_vertex, vertex)] > weight:
#         w[(next_vertex, vertex)] = weight

# # sort coods in increasing order of y
# coords.sort(key=lambda x: x[1])
# for i, (_, y, vertex) in enumerate(coords[:-1]):
#     _, next_y, next_vertex = coords[i + 1]
#     adj[vertex].add(next_vertex)
#     adj[next_vertex].add(vertex)
#     weight = next_y - y
#     if (vertex, next_vertex) not in w or w[(vertex, next_vertex)] > weight:
#         w[(vertex, next_vertex)] = weight
#     if (next_vertex, vertex) not in w or w[(next_vertex, vertex)] > weight:
#         w[(next_vertex, vertex)] = weight

# print(prim(adj, w))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
z = [tuple(map(int,input().split())) for i in range(N)]
z.sort()
y = [(z[i][1],i) for i in range(N)]
y.sort()
cost = [[] for i in range(N)]
for i in range(N):
    j = y[i][1]
    if i != 0:
        cost[i].append((i-1,z[i][0]-z[i-1][0]))
        cost[i].append((i-1,abs(z[i][1]-z[i-1][1])))
        j_ = y[i-1][1]
        cost[j].append((j_,y[i][0]-y[i-1][0]))
        cost[j].append((j_,abs(z[j][0]-z[j_][0])))
    if i != N-1:
        cost[i].append((i+1,z[i+1][0]-z[i][0]))
        cost[i].append((i+1,abs(z[i+1][1]-z[i][1])))
        j_ = y[i+1][1]
        cost[j].append((j_,y[i+1][0]-y[i][0]))
        cost[j].append((j_,abs(z[j_][1]-z[j][1])))

import heapq

def prim(cost):
    V = len(cost)
    res = 0
    mincost = [float('inf')]*V
    used = [False]*V
    hq = []
    mincost[0] = 0
    heapq.heappush(hq,(0,0))
    done = 0
    while hq:
        weight,u = heapq.heappop(hq)
        if not used[u]:
            used[u] = True
            done += 1
            res += weight
            mincost[u] = weight
            for v, v_cost in cost[u]:
                if not used[v]:
                    heapq.heappush(hq,(v_cost,v))
            if done == V:
                break
    return res

print(prim(cost))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
z = [tuple(map(int,input().split())) for i in range(N)]
z.sort()
y = [(z[i][1],i) for i in range(N)]
y.sort()
cost = [[] for i in range(N)]
for i in range(N):
    j = y[i][1]
    if i != 0:
        cost[i].append((i-1,z[i][0]-z[i-1][0]))
        cost[i].append((i-1,abs(z[i][1]-z[i-1][1])))
        j_ = y[i-1][1]
        cost[j].append((j_,y[i][0]-y[i-1][0]))
        cost[j].append((j_,abs(z[j][0]-z[j_][0])))
    if i != N-1:
        cost[i].append((i+1,z[i+1][0]-z[i][0]))
        cost[i].append((i+1,abs(z[i+1][1]-z[i][1])))
        j_ = y[i+1][1]
        cost[j].append((j_,y[i+1][0]-y[i][0]))
        cost[j].append((j_,abs(z[j_][1]-z[j][1])))

import heapq

def prim(cost):
    V = len(cost)
    res = 0
    mincost = [float('inf')]*V
    used = [False]*V
    hq = []
    mincost[0] = 0
    heapq.heappush(hq,(0,0))
    while hq:
        weight,u = heapq.heappop(hq)
        if used[u]:
            continue
        used[u] = True
        res += weight
        mincost[u] = weight
        for v, v_cost in cost[u]:
            if not used[v]:
                heapq.heappush(hq,(v_cost,v))
    return res

print(prim(cost))

Submission status: Time Limit Exceeded

Solution code:
import heapq
def cost(a, b, c, d):
    return min(abs(a-c), abs(b-d))

N = int(input())
T = []
for i in range(N):
    x, y = map(int, input().split())
    if (x, y) not in T:
        T.append((x, y))
lenT = len(T)
Tx, Ty = sorted(T, key = lambda t:t[0]), sorted(T, key = lambda t:t[1])
P = [[] for i in range(lenT)]
for i in range(lenT-1):
    xc, yc = cost(Tx[i][0], Tx[i][1], Tx[i+1][0], Tx[i+1][1]), cost(Ty[i][0], Ty[i][1], Ty[i+1][0], Ty[i+1][1])
    P[T.index(Tx[i])].append([xc, T.index(Tx[i+1])])
    P[T.index(Tx[i+1])].append([xc, T.index(Tx[i])])
    P[T.index(Ty[i])].append([yc, T.index(Ty[i+1])])
    P[T.index(Ty[i+1])].append([yc, T.index(Ty[i])])

Visit = [False for i in range(lenT)]
Visit[0] = True
Q = [p for p in P[0]]
heapq.heapify(Q)
Total = 0
while Q:
    nextCost, nextNode = heapq.heappop(Q)
    if Visit[nextNode] == False:
        Total += nextCost
        Visit[nextNode] = True
        for t in P[nextNode]:
            if Visit[t[1]] == False:
                heapq.heappush(Q, [t[0], t[1]])
print(Total)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu Sep 20 21:40:30 2018
ABC065D
@author: maezawa
i=0...n (0-origin)
"""
import heapq
import sys
input = sys.stdin.readline

n = int(input())
a = []
b = []
for i in range(n): # i is a name of the city (0-origin)
    xy = list(map(int, input().split()))
    a.append([xy[0],i])
    b.append([xy[1],i])

a.sort()
b.sort()
#print(a) 
#print(b)

# making adj list
adj = [[] for _ in range(n)]
for [x0, j0], [x1, j1]  in zip(a, a[1:]):
    adj[j0].append([x1-x0, j1])
    adj[j1].append([x1-x0, j0])
for [y0, j0], [y1, j1] in zip(b, b[1:]):
    adj[j0].append([y1-y0, j1])
    adj[j1].append([y1-y0, j0])

#print(adj)
    
# Prim's algorithm
#d = [10**10]*n
visited = [False]*n
h = []
s = 0
heapq.heappush(h, [0, s])
cnt = 0
totalcost = 0 
while h:
    cost, node = heapq.heappop(h)
    #if visited[node] != True and cost < d[node]:
    if visited[node] != True:        
        #d[node] = cost
        visited[node] = True
        totalcost += cost
        cnt += 1
        if cnt == n:
            break
        for edge in adj[node]:
            if visited[edge[1]]:
                continue
            heapq.heappush(h, edge)
            
#print(d)
print(totalcost)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu Sep 20 21:40:30 2018
ABC065D
@author: maezawa
i=0...n (0-origin)
"""
import heapq

n = int(input())
a = []
b = []
for i in range(n): # i is a name of the city (0-origin)
    xy = list(map(int, input().split()))
    a.append([xy[0],i])
    b.append([xy[1],i])

a.sort()
b.sort()
#print(a) 
#print(b)

# making adj list
adj = [[] for _ in range(n)]
for [x0, j0], [x1, j1]  in zip(a, a[1:]):
    adj[j0].append([x1-x0, j1])
    adj[j1].append([x1-x0, j0])
for [y0, j0], [y1, j1] in zip(b, b[1:]):
    adj[j0].append([y1-y0, j1])
    adj[j1].append([y1-y0, j0])

#print(adj)
    
# Prim's algorithm
#d = [10**10]*n
visited = [False]*n
h = []
s = 0
heapq.heappush(h, [0, s])
cnt = 0
totalcost = 0 
while h:
    cost, node = heapq.heappop(h)
    #if visited[node] != True and cost < d[node]:
    if visited[node] != True:        
        #d[node] = cost
        visited[node] = True
        totalcost += cost
        cnt += 1
        if cnt == n:
            break
        for edge in adj[node]:
            if visited[edge[1]] == True:
                continue
            heapq.heappush(h, edge)
            
#print(d)
print(totalcost)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu Sep 20 21:40:30 2018
ABC065D
@author: maezawa
i=0...n (0-origin)
"""
import heapq

n = int(input())
a = []
b = []
for i in range(n): # i is a name of the city (0-origin)
    xy = list(map(int, input().split()))
    a.append([xy[0],i])
    b.append([xy[1],i])

a.sort()
b.sort()
#print(a) 
#print(b)

# making adj list
adj = [[] for _ in range(n)]
for [x0, j0], [x1, j1]  in zip(a, a[1:]):
    adj[j0].append([x1-x0, j1])
    adj[j1].append([x1-x0, j0])
for [y0, j0], [y1, j1] in zip(b, b[1:]):
    adj[j0].append([y1-y0, j1])
    adj[j1].append([y1-y0, j0])

#print(adj)
    
# Prim's algorithm
d = [10**10]*n
visited = [False]*n
h = []
s = 0
heapq.heappush(h, [0, s])
cnt = 0
totalcost = 0 
while h:
    cost, node = heapq.heappop(h)
    if visited[node] != True and cost < d[node]:
    #if visited[node] != True:        
        d[node] = cost
        visited[node] = True
        totalcost += cost
        cnt += 1
        if cnt == n:
            break
        for edge in adj[node]:
            if visited[edge[1]] == True:
                continue
            heapq.heappush(h, edge)
            
#print(d)
print(totalcost)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu Sep 20 21:40:30 2018
ABC065D
@author: maezawa
i=0...n (0-origin)
"""
import heapq

n = int(input())
a = []
b = []
for i in range(n): # i is a name of the city (0-origin)
    xy = list(map(int, input().split()))
    a.append([xy[0],i])
    b.append([xy[1],i])

a.sort()
b.sort()
#print(a) 
#print(b)

# making adj list
adj = [[] for _ in range(n)]
for [x0, j0], [x1, j1]  in zip(a, a[1:]):
    adj[j0].append([x1-x0, j1])
    adj[j1].append([x1-x0, j0])
for [y0, j0], [y1, j1] in zip(b, b[1:]):
    adj[j0].append([y1-y0, j1])
    adj[j1].append([y1-y0, j0])

#print(adj)
    
# Prim's algorithm
d = [10**10]*n
visited = [False]*n
h = []
s = 0
heapq.heappush(h, [0, s])
cnt = 0
while h:
    cost, node = heapq.heappop(h)
    if visited[node] != True and cost < d[node]:
    #if visited[node] != True:        
        d[node] = cost
        visited[node] = True
        cnt += 1
        if cnt == n:
            break
        for cost1, node1 in adj[node]:
            #if visited[node1] == True:
            #    continue
            heapq.heappush(h, [cost1, node1])
            
#print(d)
print(sum(d))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu Sep 20 21:40:30 2018
ABC065D
@author: maezawa
i=0...n (0-origin)
"""
import heapq

n = int(input())
a = []
b = []
for i in range(n): # i is a name of the city (0-origin)
    xy = list(map(int, input().split()))
    a.append([xy[0],i])
    b.append([xy[1],i])

a.sort()
b.sort()
#print(a) 
#print(b)

# making adj list
adj = [[] for _ in range(n)]
for [x0, j0], [x1, j1]  in zip(a, a[1:]):
    adj[j0].append([x1-x0, j1])
    adj[j1].append([x1-x0, j0])
for [y0, j0], [y1, j1] in zip(b, b[1:]):
    adj[j0].append([y1-y0, j1])
    adj[j1].append([y1-y0, j0])

#print(adj)
    
# Prim's algorithm
d = [10**10]*n
visited = [False]*n
h = []
s = 0
heapq.heappush(h, [0, s])
cnt = 0
while h:
    cost, node = heapq.heappop(h)
    if visited[node] != True and cost < d[node]:
    #if visited[node] != True:        
        d[node] = cost
        visited[node] = True
        cnt += 1
        if cnt == n:
            break
        for cost1, node1 in adj[node]:
            if visited[node1] == True:
                continue
            heapq.heappush(h, [cost1, node1])
            
#print(d)
print(sum(d))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu Sep 20 21:40:30 2018
ABC065D
@author: maezawa
i=0...n (0-origin)
"""
import heapq

n = int(input())
a = []
b = []
for i in range(n): # i is a name of the city (0-origin)
    xy = list(map(int, input().split()))
    a.append([xy[0],i])
    b.append([xy[1],i])

a.sort()
b.sort()
#print(a) 
#print(b)

# making adj list
adj = [[] for _ in range(n)]
for [x0, j0], [x1, j1]  in zip(a, a[1:]):
    adj[j0].append([x1-x0, j1])
    adj[j1].append([x1-x0, j0])
for [y0, j0], [y1, j1] in zip(b, b[1:]):
    adj[j0].append([y1-y0, j1])
    adj[j1].append([y1-y0, j0])

#print(adj)
    
# Prim's algorithm
d = [10**10]*n
visited = [False]*n
h = []
s = 0
heapq.heappush(h, [0, s])
cnt = 0
while h:
    cost, node = heapq.heappop(h)
    if visited[node] != True and cost < d[node]:
    #if visited[node] != True:        
        d[node] = cost
        visited[node] = True
        cnt += 1
        if cnt == n:
            break
        for edge in adj[node]:
            if visited[edge[1]] == True:
                continue
            heapq.heappush(h, edge)
            
#print(d)
print(sum(d))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu Sep 20 21:40:30 2018
ABC065D
@author: maezawa
i=0...n (0-origin)
"""
import heapq

n = int(input())
a = []
b = []
for i in range(n): # i is a name of the city (0-origin)
    xy = list(map(int, input().split()))
    a.append([i,xy[0]])
    b.append([i,xy[1]])

a.sort(key=lambda x: x[1])
b.sort(key=lambda x: x[1])
#print(a) 
#print(b)

# making adj list
adj = [[] for _ in range(n)]
for [j0, x0], [j1, x1]  in zip(a, a[1:]):
    adj[j0].append([x1-x0, j1])
    adj[j1].append([x1-x0, j0])
for [j0, y0], [j1, y1] in zip(b, b[1:]):
    adj[j0].append([y1-y0, j1])
    adj[j1].append([y1-y0, j0])

#print(adj)
    
# Prim's algorithm
d = [10**10]*n
visited = [False]*n
h = []
s = 0
heapq.heappush(h, [0, s])
cnt = 0
while h:
    cost, node = heapq.heappop(h)
    if visited[node] != True and cost < d[node]:
    #if visited[node] != True:        
        d[node] = cost
        visited[node] = True
        cnt += 1
        if cnt == n:
            break
        for edge in adj[node]:
            if visited[edge[1]] == True:
                continue
            heapq.heappush(h, edge)
            
#print(d)
print(sum(d))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu Sep 20 21:40:30 2018
ABC065D
@author: maezawa
i=0...n (0-origin)
"""
import heapq

n = int(input())
a = []
b = []
for i in range(n): # i is a name of the city (0-origin)
    xy = list(map(int, input().split()))
    a.append([i,xy[0]])
    b.append([i,xy[1]])

a.sort(key=lambda x: x[1])
b.sort(key=lambda x: x[1])
#print(a) 
#print(b)

# making adj list
adj = [[] for _ in range(n)]
for i, [j, x] in enumerate(a[:-1]):
    adj[j].append([a[i+1][1]-x, a[i+1][0]])
    adj[a[i+1][0]].append([a[i+1][1]-x, j])
for i, [j, y] in enumerate(b[:-1]):
    adj[j].append([b[i+1][1]-y, b[i+1][0]])
    adj[b[i+1][0]].append([b[i+1][1]-y, j])

#print(adj)
    
# Prim's algorithm
d = [10**10]*n
visited = [False]*n
h = []
s = 0
heapq.heappush(h, [0, s])
cnt = 0
while h:
    cost, node = heapq.heappop(h)
    if visited[node] != True and cost < d[node]:
    #if visited[node] != True:        
        d[node] = cost
        visited[node] = True
        cnt += 1
        if cnt == n:
            break
        for edge in adj[node]:
            if visited[edge[1]] == True:
                continue
            heapq.heappush(h, edge)
            
#print(d)
print(sum(d))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu Sep 20 21:40:30 2018
ABC065D
@author: maezawa
i=0...n (0-origin)
"""
import heapq

n = int(input())
a = []
b = []
for i in range(n): # i is a name of the city (0-origin)
    xy = list(map(int, input().split()))
    a.append([i,xy[0]])
    b.append([i,xy[1]])

a.sort(key=lambda x: x[1])
b.sort(key=lambda x: x[1])
#print(a) 
#print(b)

# making adj list
adj = [[] for _ in range(n)]
for i, [j, x] in enumerate(a[:-1]):
    adj[j].append([a[i+1][1]-x, a[i+1][0]])
    adj[a[i+1][0]].append([a[i+1][1]-x, j])
for i, [j, y] in enumerate(b[:-1]):
    adj[j].append([b[i+1][1]-y, b[i+1][0]])
    adj[b[i+1][0]].append([b[i+1][1]-y, j])

#print(adj)
    
# Prim's algorithm
d = [10**10]*n
visited = [False]*n
h = []
s = 0
heapq.heappush(h, [0, s])
cnt = 0
while h:
    cost, node = heapq.heappop(h)
    #if visited[node] != True and cost < d[node]:
    if visited[node] != True:        
        d[node] = cost
        visited[node] = True
        cnt += 1
        if cnt == n:
            break
        for edge in adj[node]:
            if visited[edge[1]] == True:
                continue
            heapq.heappush(h, edge)
            
#print(d)
print(sum(d))