Page MenuHomec4science
Files F94105532

problemB.py
No OneTemporary
Actions

File Metadata

Created
Tue, Dec 3, 23:11

problemB.py
View Options

#!/usr/bin/python
# n nodes: cities
# m nodes: road linking cities
# 1 = north pole
# n = south pole
#from heapq import heapify, heappush, heappop
import heapq
# TASK: find minimum required temperature shield
class EnumGraph:
def __init__(self, n, E):
self.n = n
self.E = E
def __len__(self):
return self.n
def parseinput(fstream):
line = fstream.readline().split(' ')
n = int(line[0]) # number of nodes
m = int(line[1]) # number of edges
# Setup E representation
E = [[] for i in range(n)]
for i in range(m):
line = fstream.readline().split(' ')
a = int(line[0])
b = int(line[1])
w = int(line[2])
# convention: (weight, node)
E[a-1].append((w, b-1))
E[b-1].append((w, a-1))
return EnumGraph(n, E)
def print_path(P, G):
index = P[-1]
while index > 0:
n = P[index]
print("%d -> %d: %d" % (index, n, G.A[index][n]))
index = n
# maximum weight over a single path
# minimum over all paths
def minimum_shielding(G):
n = G.n
# dijkstra priority queue
pq = []
heapq.heappush(pq, (0, 0))
# distances
distances = [sys.maxsize for i in range(n)]
distances[0] = -sys.maxsize # maximal weight
# parents
parents = [0 for i in range(n)]
while len(pq) > 0:
# find maximum over priority queue
city = heapq.heappop(pq)
# extract node identifier and distance from City structure
u = city[1]
for (w, v) in G.E[u]:
# find minimum over connecting edges weights
d = min(max(distances[u], w), distances[v])
if d < distances[v]:
#print("Comparison %d --> %d" % ((u+1),(v+1)), ", Distance: %d vs %d" % (d, distances[v]))
distances[v] = d
# track parent
parents[v] = u
heapq.heappush(pq, (d,v)) # analyse v next
return distances[-1]
import sys
graph = parseinput(sys.stdin)
print(minimum_shielding(graph))

Event Timeline

c4science · Help