CCC 2015 S4 - Convex Hull

1# CCC 2015 Senoir 4: Convex Hull2#3# written by Daniel Whitney, Newmarket High School4#5# NOTE: This is in python 3, tho I believe it would take very little6#       to convert it to python 2 (switch range to xrange, print() to7#       print).8#9# This problem being a shortest path problem, I used Dijkstra's algorithm10# with some modifications to find it.11# Read:12#    en.wikipedia.org/wiki/Dijkstra's_algorithm#Algorithm13# for a quick description of how the basic algorithm works.14#15# From now on I am going to assume you know how Dijkstra's algorithm works16# so I can explain the modifications.17#18# First we have to recognize instead of simply storing the minimum19# distance to each island, we are going to have to store the minimum20# distance with X (X is 1 to 200) hull remaining to each point.  And when21# we would add a point to the que that has a negative or zero hull value,22# we simply skip it.  Thes additional states simply add more nodes to the23# graph, but when we're checking for the endpoint we check only to see if24# the current island is the correct ending island.  In this case the first25# time the ending island is removed from the que, we know we've found the26# smallest distance.27#28# For implementing the binary trees, refer to:29#    en.wikipedia.org/wiki/Binary_heap#Heap_operations30#31# I found this page explained them fairly thoroughly.32 33 34 35def pop(heap):36    popped = heap[0]37    heap[0] = heap[-1]38    heap.pop()39    lq = len(heap)40    node = 041    while node < lq:42        minimum = heap[node]43        nxt_node = node44        l_node = node*2+145        r_node = node*2+246        if l_node < lq and heap[l_node] < minimum:47            minimum = heap[l_node]48            nxt_node = l_node49        if r_node < lq and heap[r_node] < minimum:50            minimum = heap[r_node]51            nxt_node = r_node52        if node != nxt_node:53            heap[node], heap[nxt_node] = heap[nxt_node], heap[node]54            node = nxt_node55        else:56            node = lq57    return popped58 59 60def push(heap, item):61    heap.append(item)62    lq = len(heap)63    node = lq-164    while node > 0:65        nxt_node = (node-1)//266        if heap[nxt_node] > heap[node]:67            heap[node], heap[nxt_node] = heap[nxt_node], heap[node]68            node = nxt_node69        else:70            node = 071 72 73file = open('s4.15.in')74K, N, M = map(int, file.readline().split())75routes = [{} for n in range(N)]76for m in range(M):77    a, b, t, h = map(int, file.readline().split())78    routes[a-1].setdefault(b-1, []).append((t, h))79    routes[b-1].setdefault(a-1, []).append((t, h))80 81 82INF = 10**1083 84 85p, q = map(int, file.readline().split())86p, q = p-1, q-187 88min_time = INF89distance = [[INF for i in range(200+1)] for n in range(N)]90distance[p][K] = 091visited = set()92que = [(0, p, K)]93while que:94    island = pop(que)95    if island[1] == q:96        min_time = island[0]97        break98    if island[1:] in visited:99        continue100    visited.add(island[1:])101    for destination in routes[island[1]]:102        for route in routes[island[1]][destination]:103            to_add = (distance[island[1]][island[2]] + route[0], destination, island[2] - route[1])104            if to_add[2] > 0:105                if to_add[0] < distance[to_add[1]][to_add[2]]:106                    distance[to_add[1]][to_add[2]] = to_add[0]107                push(que, to_add)108if min_time == INF:109    min_time = -1110 111print(min_time)112