제출 #31216

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
31216		leejseo	주유소 (KOI16_gas)	Pypy 2	0 / 100	3 ms	1 KiB

gas

from heapq import *
import itertools

MAX_INT = int(9E18)


class PriorityQueue:
    def __init__(self):
        self.pq = []                         # list of entries arranged in a heap
        self.entry_finder = {}               # mapping of tasks to entris
        self.REMOVED = '<removed-task>'      # placeholder for a removed task
        self.counter = itertools.count()     # unique sequence count

    def add_task(self, task, priority=0):
        #'Add a new task or update the priority of an existing task'
        if task in self.entry_finder:
            self.remove_task(task)
        count = next(self.counter)
        entry = [priority, count, task]
        self.entry_finder[task] = entry
        heappush(self.pq, entry)

    def remove_task(self, task):
        #'Mark an existing task as REMOVED.  Raise KeyError if not found.'
        entry = self.entry_finder.pop(task)
        entry[-1] = self.REMOVED

    def pop_task(self):
        #'Remove and return the lowest priority task. Raise KeyError if empty.'
        while self.pq:
            priority, count, task = heappop(self.pq)
            if task is not self.REMOVED:
                del self.entry_finder[task]
                return task
        raise KeyError('pop from an empty priority queue')
    
    def empty(self):
        if self.pq : return False
        return True
    
    def top(self):
        h = min(self.pq)
        return h[2]

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

class Node_PQ :
    def __init__ (self, u, dist):
        self.u = u
        self.dist = dist
    
    def small(b):
        return self.dist > b.dist

def cmp_node(a, b):
    if a.small(b) : return -1
    if b.small(a) : return 1
    return 0

def dijkstra(V, start, adj_list):
    #V: NUMBER OF VERTICES
    #START FROM ZERO
    Q = PriorityQueue()
    dist = [MAX_INT for i in range(V)]
    dist[start] = 0
    Q.add_task(Node_PQ(start, 0), 0)
    
    while not(Q.empty()):
        u = Q.top().u
        dist_u = Q.top().dist
        Q.pop_task()
        
        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
                Q.add_task(Node_PQ(v, dist_v), dist_v)
    return dist

def solve(V, graph, oil):
    cost_graph = [ [] for i in range(V)]
    for i in range(V):
        dist = dijkstra(V, i, graph)
        for j in range(V):
            if j == i or dist[j] == MAX_INT :
                continue
            cost = dist[j] * oil[i]
            cost_graph[i].append(Edge(j, cost))
    return dijkstra(V, 0, cost_graph)[V-1]

def main():
    V, E = map(int, raw_input().split())
    graph = [ [] for i in range(V)]
    oil = map(int, raw_input().split())
    for i in range(E):
        fr, to, weight = map(int, raw_input().split())
        fr -= 1
        to -= 1
        graph[fr].append(Edge(to, weight))
        graph[to].append(Edge(fr, weight))
    #r = dijkstra(V, 2, graph)    
    r = solve(V, graph, oil)
    print r
    return
main()

• Subtask 1: 0 / 18
• Subtask 2: 0 / 15
• Subtask 3: 0 / 16
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27