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()
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
3 ms |
1 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
2 ms |
1 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
2 ms |
1 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
3 ms |
1 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
3 ms |
1 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
