# Problem 28 - Inefficient Bus # Expected output: TIME_LIMIT_EXCEEDED # This solves the second version of the problem, which states that at no crossing the bus should take the road that is on the shortest path from that crossing to the destination crossing # Very slow read of the graph import sys from collections import deque from heapq import heappush, heappop MIN_EDGES = 1 MIN_VERTICES = 1 MAX_EDGES = 10**6 MAX_VERTICES = 10**5 + 1 MIN_VERTEX_ID = 0 MAX_VERTEX_ID = 10**5 - 1 MIN_D = 1 MAX_D = 500000000 NO_SOLUTION = "impossible" START_ID = 0 DESTINATION_ID = 1 instr = sys.stdin class graph: def __init__(self): self.edges = [] self.vertices = [] def __init__(self, vertices, edges): self.vertices = vertices self.edges = edges def __str__(self): result = "" result += "Vertices:\n" for v in self.vertices: result += "\t" + str(v) + "\n" result += "Edges:\n" for e in self.edges: result += "\t" + str(e) + "\n" return result def __repr__(self): return self.__str__() class vertex: def __init__(self, id): self.id = id self.edges = [] self.bfparent = None self.parent = None self.dist = 0 self.length = 1 def __str__(self): # return "(" + str(self.id) + ", dist: " + str(self.dist) + ")" return "(" + str(self.id) + ")" def __repr__(self): return self.__str__() def __eq__(self, other): return (isinstance(other, self.__class__) and self.id == other.id) def __ne__(self, other): return not self.__eq__(other) def __hash__(self): return self.id # Operator overloads for Dijkstra def __lt__(self, other): return self.dist < other.dist def __gt__(self, other): return self.dist > other.dist def __le__(self, other): return self.dist <= other.dist def __ge__(self, other): return self.dist >= other.dist class edge: def __init__(self, id, v1, v2, d): self.id = id self.v1 = v1 self.v2 = v2 self.d = d def connected(self, vertex): return self.v1.id == vertex.id or self.v2.id == vertex.id def __str__(self): return "[{} <-> {}]({}; {})".format(self.v1, self.v2, self.id, self.d) def __repr__(self): return self.__str__() def __eq__(self, other): return (isinstance(other, self.__class__) and self.__dict__ == other.__dict__) def __ne__(self, other): return not self.__eq__(other) def __hash__(self): return self.v1.id + self.v2.id * MAX_VERTICES def solve(): while True: g = read_graph() if g is None: return input_check_connected(g) input_check_duplicate_edges(g) dijkstra(g) if not breadth_first(g): print(NO_SOLUTION) # Find the shortest routes from the destination node to all the other nodes def dijkstra(gr, no_remove = False): heap = [] for v in gr.vertices: v.dist = MAX_D + 1 if v.id == DESTINATION_ID: heappush(heap, v) v.parent = None v.dist = 0 v_current = None while len(heap) > 0: v_prev = v_current v_current = heappop(heap) for e in v_current.edges: if e.v1.id != v_current.id: dist = e.d + v_current.dist if dist < e.v1.dist: e.v1.dist = dist e.v1.parent = v_current heappush(heap, e.v1) else: dist = e.d + v_current.dist if dist < e.v2.dist: e.v2.dist = dist e.v2.parent = v_current heappush(heap, e.v2) def breadth_first(gr): startIndex = 0 i = 0 for v in gr.vertices: if v.id == START_ID: startIndex = i break i = i + 1 v_current = gr.vertices[startIndex] queue = deque() queue.append(gr.vertices[startIndex]) visited = set([]) while len(queue) > 0: v_current = queue.popleft() if v_current.bfparent != None: v_current.length = v_current.bfparent.length + 1 if v_current.id == DESTINATION_ID: break visited.add(v_current.id) for e in v_current.edges: if e.v1.id != v_current.id and (not v_current.parent or v_current.parent.id != e.v1.id): if e.v1.id in visited: continue queue.append(e.v1) e.v1.bfparent = v_current elif e.v2.id != v_current.id and (not v_current.parent or v_current.parent.id != e.v2.id): if e.v2.id in visited: continue queue.append(e.v2) e.v2.bfparent = v_current if v_current.id == DESTINATION_ID: sys.stdout.write(str(v_current.length)) queue.clear() while v_current != None: queue.append(v_current) v_current = v_current.bfparent while len(queue) > 0: v_current = queue.pop() sys.stdout.write(' ' + str(v_current.id)) sys.stdout.write('\n') return True return False def read_graph(): input = instr.readline() if not input: return None inputs = input.split(' ') try: n = int(inputs[0]) except ValueError: raise Exception("Expected integer while reading number of crossings") if n < MIN_VERTICES or n > MAX_VERTICES: raise Exception("Input value [n] is out of range: {}".format(n)) try: m = int(inputs[1]) except ValueError: raise Exception("Expected integer while reading number of roads") if m < MIN_EDGES or m > MAX_EDGES: raise Exception("Input value [m] is out of range: {}".format(m)) edges = [] vertices = [] edgeset = set([]) verticeset = set([]) for i in range(1, m + 1): input = instr.readline() inputs = input.split(' ') n_s1 = int(inputs[0]) n_s2 = int(inputs[1]) n_d = int(inputs[2]) assert n_s1 >= MIN_VERTEX_ID and n_s1 <= MAX_VERTEX_ID assert n_s2 >= MIN_VERTEX_ID and n_s2 <= MAX_VERTEX_ID assert n_s1 != n_s2 assert n_d >= MIN_D and n_d <= MAX_D v1 = vertex(n_s1) v2 = vertex(n_s2) if v1 not in verticeset: vertices.append(v1) verticeset.add(v1) else: v1 = vertices[vertices.index(v1)] if v2 not in verticeset: vertices.append(v2) verticeset.add(v2) else: v2 = vertices[vertices.index(v2)] # Make sure that n_s1 < n_s2 so as to make the merging of edges easier if v1.id > v2.id: v1,v2 = v2,v1 # Swap e = edge(i, v1, v2, n_d) assert e not in edgeset edges.append(e) edgeset.add(e) v1.edges.append(e) v2.edges.append(e) assert(len(vertices) == n) assert(len(edges) == m) return graph(vertices, edges) def input_check_duplicate_edges(gr): parsed_edges = set() for e in gr.edges: assert e.__hash__() not in parsed_edges parsed_edges.add(e.__hash__()) def input_check_connected(gr): to_search = set([gr.vertices[0]]) visited = set() while len(to_search) > 0: v = to_search.pop() visited.add(v) for e in v.edges: start = e.v1 end = e.v2 if (e.v1 != v and e.v1 not in visited): if e.v1 not in to_search: to_search.add(e.v1) if (e.v2 != v and e.v2 not in visited): if e.v2 not in to_search: to_search.add(e.v2) assert len(visited) == len(gr.vertices) def main(): solve() if __name__ == "__main__": main()