#include <iostream> #include <fstream> #include <sstream> #include <utility> #include <vector> #include <limits> #include <map> #include <set> using namespace std; /* SANITY CHECK: assertion macro for verifying input data and internal state */ #define ASSERT(e) { if(!(e)) { cerr << #e << endl; throw; } } /* Maximum edge cost; used to indicate that a node is unreachable */ #define MAXCOST (numeric_limits<int>::max()) /* * This adjacency list data structure holds the list of all edges in the data * set (and associated "aging" costs; years "gained back" are negative cost * edges). It maps a (departure, arrival) pair to the years aged by traveling * through the wormhole. It also contains "implicit" edges that represent * having to wait for some number of years while a new wormhole arrives. * */ typedef pair<int, int> edge_t; typedef map<edge_t, int> costmap_t; /* * Use the Bellman-Ford algorithm to find the shortest path from start year * to end year and return the total cost along that path. Becuase the graph * contains negative cost edges, the less efficient Bellman-Ford algorithm * must be used instead of Dijkstra's algorithm because Dijkstra's optimizes * too early and could produce incorrect results. We also don't need an * explicit check for negative cost cycles because the problem statement * simply won't allow them. */ int findpath(costmap_t &costmap, set<int> &years, int start, int end) { map<int, int> dist; map<int, int> pred; /* Initialize "shortest path distance" map to default "unreachable" cost */ for(set<int>::iterator i = years.begin(); i != years.end(); ++i) { dist[*i] = MAXCOST; } /* The node we start from is 0 years away by definition */ dist[start] = 0; /* * Run the main body of the Bellman-Ford algorithm. Note that we could * break out of the loop as soon as a complete iteration makes no * more changes to the "dist" map. However, looping the full amount * helps establish the maximum running time for the algorithm. */ for(int i = 0; i < years.size() - 1; i++) { for(costmap_t::iterator j = costmap.begin(); j != costmap.end(); ++j) { if(dist[j->first.first] != MAXCOST) { int cost = dist[j->first.first] + j->second; if(cost < dist[j->first.second]) { dist[j->first.second] = cost; pred[j->first.second] = j->first.first; } } } } /* * DEBUG ONLY: Show the shortest path by highlighting the nodes on the * path in the Graphiviz output file. */ #ifdef DEBUG if(dist[end] != MAXCOST) { int i, j; cerr << end; for(i = end; pred.find(i) != pred.end(); i = j) { j = pred[i]; cerr << " <<" << costmap[edge_t(j, i)] << "<< "; cerr << j; } cerr << " = " << dist[end] << endl; } #endif return dist[end]; } /* Main body of program */ void process(void) { int data_num, data_idx; /* Read how many data sets to process */ cin >> data_num; /* Process each data set separately */ for(data_idx = 0; data_idx < data_num; data_idx++) { set<int> years; /* Any year seen in input; all nodes in graph */ vector<int> agents; /* List of destinations for each agent */ costmap_t costs; /* Adjecency list of wormholes & implicit waits */ int start; /* Starting year for all agents */ #ifdef DEBUG /* DEBUG ONLY: Write a graph representation to "dot" file */ ostringstream filename; filename << "time-travel" << data_idx + 1 << ".dot"; ofstream graph(filename.str().c_str(), ios::trunc); graph << "digraph G {" << endl; #endif /* Read in total number of wormholes W */ int hole_num, hole_idx; cin >> hole_num; ASSERT(1 <= hole_num && hole_num <= 100); /* Read in the list of wormholes for this data set */ for(hole_idx = 0; hole_idx < hole_num; hole_idx++) { int depart, arrive, cost; cin >> depart >> arrive; ASSERT(1 <= depart && depart <= 9999); ASSERT(1 <= arrive && arrive <= 9999); /* Add to set of all nodes in graph; usef for implicit edges */ years.insert(depart); years.insert(arrive); /* Compute wormhole traveling costs (negative for backwards) */ if(depart <= arrive) { cost = (arrive - depart) / 2; } else { cost = (arrive - depart) / 4; } /* Record the cost in the adjacency list */ costs[edge_t(depart, arrive)] = cost; #ifdef DEBUG graph << " " << depart << " -> " << arrive << " [label=" << cost << "]" << endl; #endif } /* Read in the starting year */ cin >> start; ASSERT(1 <= start && start <= 9999); years.insert(start); #ifdef DEBUG graph << " " << start << " [label=\"" << start << "\\n(S)\"]" << endl; #endif /* Read in total number of missions/agents M */ int agent_num, agent_idx; cin >> agent_num; ASSERT(1 <= agent_num && agent_num <= 100); /* Read in the list of final destinations for each agent */ for(agent_idx = 0; agent_idx < agent_num; agent_idx++) { int dest; cin >> dest; ASSERT(1 <= dest && dest <= 9999); #ifdef DEBUG graph << " " << dest << " [label=\"" << dest << "\\n(" << agent_idx + 1 << ")\"]" << endl; #endif years.insert(dest); agents.push_back(dest); } /* * For every pair of years (X, Y) in the input such that X < Y, compute * an "implicit" edge that represents having to wait from year X to * year Y if there was no explicit wormhole edge (X, Y) in data set. * Note that STL sets are already in ascending order therefore an * explicit sort() is not required. */ set<int>::iterator i, j; for(i = j = years.begin(), ++j; j != years.end(); ++i, ++j) { edge_t edge(*i, *j); if(costs.find(edge) == costs.end()) { costs[edge] = *j - *i; #ifdef DEBUG graph << " " << *i << " -> " << *j << " [label=" << *j - *i << ", style=dashed]" << endl; #endif } } /* Print the data set label */ cout << "DATA SET #" << data_idx + 1 << endl; #ifdef DEBUG cerr << "DATA SET #" << data_idx + 1 << endl; #endif /* * Now for each mission, compute the cost of traveling from the * start to destination year and back. If that cost is less than * MAXCOST then the mission is possible. */ for(agent_idx = 0; agent_idx < agent_num; agent_idx++) { int end = agents[agent_idx]; int travelcost = findpath(costs, years, start, end); int returncost = findpath(costs, years, end, start); int totalcost; if(travelcost == MAXCOST || returncost == MAXCOST) { cout << "IMPOSSIBLE" << endl; #ifdef DEBUG cerr << "IMPOSSIBLE" << endl; #endif } else { cout << travelcost + returncost << endl; #ifdef DEBUG cerr << travelcost + returncost << endl; #endif } #ifdef DEBUG graph << "}" << endl; graph.close(); #endif } } } /* Run program and print out any exceptions that occur */ int main(void) { /* Throw exceptions on EOF or failed data extraction in >> operator */ cin.exceptions(ios::eofbit | ios::failbit); /* Run main body of code */ try { process(); } /* Catch unexpected EOF or bad input data */ catch(ios::failure const &e) { cerr << "Unexpected EOF or data type mismatch on input" << endl; } return 0; }