#!/usr/bin/env python# Time Travel# Phil Bordelonimportosimportsys DEBUG = os.getenv("DEBUG", False) EARLIEST_YEAR = 1 LATEST_YEAR = 9999# Are you surprised to find a class doubling as a struct here? I hope not.classStruct():pass##### bellmanFord ... uh ... yeah. While predecessor edges aren't used,# we track them so that we can print a nice debug path.defbellmanFord(vertex_list, edge_list, start, finish):# A set of vertex objects, initialized to an infinite distance away.real_vertices = {}forvertexinvertex_list: real_vertex =Struct() real_vertex.year = vertexifvertex == start: real_vertex.distance = 0else: real_vertex.distance = LATEST_YEAR + 1 real_vertex.predecessor = None real_vertices[vertex] = real_vertexforiinrange(len(vertex_list) - 1):foredgeinedge_list: one_end = real_vertices[edge[0]] other_end = real_vertices[edge[1]]ifother_end.distance > one_end.distance + edge[2]: other_end.distance = one_end.distance + edge[2] other_end.predecessor = one_endifDEBUG: to_whilecurr_vertex.predecessor: to_returnreal_vertices[finish].distance##### travelThroughTime simulates time travel, considerably less interestingly# than I suspect the real thing would be.deftravelThroughTime(universe, goal_year):# Time travel takes place in two phases: start year to goal year, then# goal year back to start year. We're going to use copies of the universe# vertex/edge data so as not to clutter it up with unnecessary edges, plus# the relaxation process will obviously muck with the structures anyways.vertex_list = universe.vertex_list[:] edge_list = universe.edge_list[:]# If the goal year isn't already an entry in the vertex list, make it so.ifgoal_yearnotinvertex_list: vertex_list.append(goal_year)# Sort the vertex list ...vertex_list.sort()# And now we add the slow, boring, 1-year-per-year travels of Real Time(tm)# to the edge list, basically adding an edge between each subsequent year# of the difference between those years. We only care about 'key' years,# such as ones with wormholes or start/ends, so this works nicely.foriinrange(len(vertex_list) - 1): edge_list.append((vertex_list[i], vertex_list[i + 1], vertex_list[i + 1] - vertex_list[i]))# Now we actually run Bellman-Ford across this puppy. B-F will make its# own fresh copies of the lists to not mess with stuff, and return the# distance. How very nice of it!there =bellmanFord(vertex_list, edge_list, universe.start_year, goal_year) back =bellmanFord(vertex_list, edge_list, goal_year, universe.start_year)return(there + back)defmain(): dataset_count =int(sys.stdin.readline())fordataset_loopinrange(dataset_count):Struct()# Get the number of wormholes in this universe.universe.wormhole_count =int(sys.stdin.readline()) universe.edge_list = [] universe.vertex_list = []# Read in each wormhole, adding them as edges. We also track the# furthest in the future a wormhole can be entered, and the furthest# in the past one can be exited, as no missions beyond those years# can be handled, and all missions in between those can.latest_entrance = EARLIEST_YEAR - 1 earliest_exit = LATEST_YEAR + 1foriinrange(universe.wormhole_count): entrance, exit = [int(x)forxinsys.stdin.readline().strip().split()]ifDEBUG:# Add the entrance and exit to the vertex list.forjinentrance, exit:ifjnotinuniverse.vertex_list: universe.vertex_list.append(j)ifentrance < exit:# Forward wormhole. Halve the time passed.edge_weight = (exit - entrance) / 2 universe.edge_list.append((entrance, exit, edge_weight))ifDEBUG:elifexit < entrance:# Backwards wormole. Negative quarter time.edge_weight = -((entrance - exit) / 4) universe.edge_list.append((entrance, exit, edge_weight))ifDEBUG:else:# We don't care about NOP wormholes.pass# Update our latest entrances and earliest exits if appropriate.iflatest_entrance < entrance: latest_entrance = entranceifearliest_exit > exit: earliest_exit = exitifDEBUG:# Get the start year.universe.start_year =int(sys.stdin.readline())ifuniverse.start_yearnotinuniverse.vertex_list: universe.vertex_list.append(universe.start_year)# Now, let's handle the missions.mission_count =int(sys.stdin.readline())formission_loopinrange(mission_count): goal_year =int(sys.stdin.readline())# A mission is undoable only if either the start year is out of# the network of wormholes or the destination year is out of# the network of wormholes. Don't even bother trying to compute# if those are the case ... except for when the goal year is the# same as the start year. This is a trivial corner case.if(universe.start_year < earliest_exitoruniverse.start_year > latest_entranceorgoal_year < earliest_exitorgoal_year > latest_entrance):ifuniverse.start_year != goal_year:else:else:# Time travel, baby!time_taken =travelThroughTime(universe, goal_year)repr(time_taken))if"__main__" == __name__:main()