Submission #35684

#	Time	Username	Problem	Language	Result	Execution time	Memory
35684		leejseo	Jakarta Skyscrapers (APIO15_skyscraper)	Cpython 2	57 / 100	1067 ms	40 KiB

skyscraper

#-*- coding: utf-8 -*-
from heapq import *
from bisect import bisect_right
maxint = int(2E9)

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 binary_search(L, val):
    if not L : return False
    s = bisect_right(L, val)
    return L[s-1] == val

def dijkstra(start):
    global N, M, V, B, P
    dist = [maxint for i in range(N)]    
    start = B[0]
    dist[start] = 0
    Q = []
    heappush(Q, Node(start, 0))
    while Q :
        #### priority queue is not empty ####
        node = heappop(Q)
        u, dist_u = node.u, node.dist
        if dist_u > dist[u] : continue
        for power in V[u]:
            #### u에 power 만큼의 힘을 가진 도게가 있음 ####
            #### 오른쪽으로 탐색을 진행 ####
            to = u+power
            cost = dist_u + 1
            while to < N : #### 목적지의 빌딩번호가 N보다 커지면 안됨 ####
                if dist[to] > cost :
                    dist[to] = cost
                    heappush(Q, Node(to, cost))
                    if binary_search(V[to], power):
                        """
                        V[o]에 p만큼의 힘을 가진 도게가 있으므로,
                        이 도게가 더 가는 것이나 이미 V[o]에 있는 도게가 더 가는 것이나
                        equivalent함
                        따라서, 중복탐색을 하지 않는 것이 더 효율적임
                        """
                        break
                to += power
                cost += 1
            #### 왼쪽으로 탐색을 진행 ####
            to = u-power
            cost = dist_u + 1
            while to >= 0 : #### 목적지의 빌딩번호가 0보다 작아지면 안됨 ####
                if dist[to] > cost :
                    dist[to] = cost
                    heappush(Q, Node(to, cost))
                    if binary_search(V[to], power):
                        """
                        V[o]에 p만큼의 가진 도게가 있으므로 이 도게가 더 가는 것이나
                        V[o]에 있는 도게가 더 가는 것이나 equivalent함
                        따라서, 중복탐색을 하지 않는 것이 더 효율적임
                        """
                        break
                to -= power
                cost += 1
    return dist

def main():
    global N, M, V, B, P   
    """
    V : VERTICES의 집합; V[i][j]는 i라는 빌딩에서 j라는 power를 가진게 있다는걸 의미함
    P : POWER; B : BUILDING;
    """

    N, M = map(int, raw_input().split())
    V = [ [] for i in range(N) ]
    B = [None for i in range(M)]
    P = [None for i in range(M)]
    for i in range(M):
        B[i], P[i] = map(int, raw_input().split())
        V[B[i]].append(P[i])
        
    for i in range(N):
        V[i] = list(set(V[i]))
        V[i].sort()
    start = B[0]
    dist = dijkstra(start)
    ans = dist[B[1]]
    if ans == maxint: print -1
    else: print ans
    return
main()

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