Submission #34225

#	Time	Username	Problem	Language	Result	Execution time	Memory
34225		leejseo	Jakarta Skyscrapers (APIO15_skyscraper)	Cpython 2	10 / 100	1072 ms	53 KiB

skyscraper

from heapq import *
MAX_INT = int(2E9)

class Edge(object):
    def __init__(self, to, weight):
        self.to = to
        self.weight = weight

class Node(object):
    def __init__(self, u, dist):
        self.u = u
        self.dist = dist
    
    def __cmp__(self, other):
        return cmp(self.dist, other.dist)


def dijkstra(V, start, adj_list):
    Q = []
    dist = [MAX_INT for i in range(V)]
    dist[start] = 0
    heappush(Q, Node(start, 0))
    while Q:
        u = Q[0].u
        dist_u = Q[0].dist
        heappop(Q)
        if dist[u] < dist_u :
            continue
        for i in range(len(adj_list[u])):
            v = adj_list[u][i].to
            dist_v = dist_u + adj_list[u][i].weight
            
            if dist_v < dist[v]:
                dist[v] = dist_v
                heappush(Q, Node(v, dist_v))
    return dist

N, M = map(int, raw_input().split())
doge = [None]*M
for i in range(M):
    doge[i] = map(int, raw_input().split())

adj_list = [ [] for i in range(M) ]

for i in range(M):
    for j in range(M):
        if i != j and ((doge[i][0] - doge[j][0])%doge[i][1] == 0 ):
            adj_list[i].append(Edge(j, abs(doge[i][0] - doge[j][0])/doge[i][1]))

ans = dijkstra(M, 0, adj_list)

if ans[1] == MAX_INT:
    print -1
else:
    print ans[1]

• Subtask 1: 10 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43