oj.uz

답안 #31218

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
31218 2017-08-14T02:34:25 Z leejseo 주유소 (KOI16_gas) Python 2
18 / 100
 1065 ms 46 KB 
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 = (self.pq)[0]
        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
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 2 KB Output is correct
2 Correct 18 ms 3 KB Output is correct
3 Correct 17 ms 3 KB Output is correct
4 Correct 18 ms 3 KB Output is correct
5 Correct 19 ms 3 KB Output is correct
6 Correct 23 ms 3 KB Output is correct
7 Correct 17 ms 3 KB Output is correct
8 Correct 17 ms 3 KB Output is correct
9 Correct 15 ms 3 KB Output is correct
10 Correct 16 ms 3 KB Output is correct
11 Correct 16 ms 3 KB Output is correct
12 Correct 16 ms 3 KB Output is correct
13 Correct 16 ms 3 KB Output is correct

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1010 ms 45 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 966 ms 46 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 2 KB Output is correct
2 Correct 18 ms 3 KB Output is correct
3 Correct 17 ms 3 KB Output is correct
4 Correct 18 ms 3 KB Output is correct
5 Correct 19 ms 3 KB Output is correct
6 Correct 23 ms 3 KB Output is correct
7 Correct 17 ms 3 KB Output is correct
8 Correct 17 ms 3 KB Output is correct
9 Correct 15 ms 3 KB Output is correct
10 Correct 16 ms 3 KB Output is correct
11 Correct 16 ms 3 KB Output is correct
12 Correct 16 ms 3 KB Output is correct
13 Correct 16 ms 3 KB Output is correct
14 Runtime error 1065 ms 46 KB Execution failed because the return code was nonzero
15 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 2 KB Output is correct
2 Correct 18 ms 3 KB Output is correct
3 Correct 17 ms 3 KB Output is correct
4 Correct 18 ms 3 KB Output is correct
5 Correct 19 ms 3 KB Output is correct
6 Correct 23 ms 3 KB Output is correct
7 Correct 17 ms 3 KB Output is correct
8 Correct 17 ms 3 KB Output is correct
9 Correct 15 ms 3 KB Output is correct
10 Correct 16 ms 3 KB Output is correct
11 Correct 16 ms 3 KB Output is correct
12 Correct 16 ms 3 KB Output is correct
13 Correct 16 ms 3 KB Output is correct
14 Runtime error 1010 ms 45 KB Execution failed because the return code was nonzero
15 Halted 0 ms 0 KB -