Advertisement
VSZM

TSHPATH in SPOJ

Jul 7th, 2014
337
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Text;
  4.  
  5. namespace Turtles_shortest_path
  6. {
  7.     interface Operator
  8.     {
  9.         State apply(State s);
  10.         int Expense(State s);
  11.     }
  12.  
  13.     interface State
  14.     {
  15.         List<Operator> ApplicableOperators();
  16.         bool IsGoal();
  17.     }
  18.  
  19.     interface Problem
  20.     {
  21.         State StartState();
  22.     }
  23.  
  24.  
  25.     class Travel : Operator
  26.     {
  27.         public int From { get; private set; }
  28.         public int To { get; private set; }
  29.         public int Cost { get; private set; }
  30.  
  31.         public Travel(int from, int to, int cost)
  32.         {
  33.             From = from;
  34.             To = to;
  35.             Cost = cost;
  36.         }
  37.         public State apply(State s)
  38.         {
  39.             return new City(To, Shortest_Path_Problem.cities_and_their_neighbours[To]);
  40.         }
  41.  
  42.  
  43.         public int Expense(State s)
  44.         {
  45.             return Cost;
  46.         }
  47.     }
  48.  
  49.     class City : State
  50.     {
  51.         private Dictionary<int, int> routes;
  52.         public int CityID { get; set; }
  53.         public bool IsGoal()
  54.         {
  55.             return this.CityID == Shortest_Path_Problem.DestinationID;
  56.         }
  57.  
  58.  
  59.         public City(int id, Dictionary<int, int> travel_costs)
  60.         {
  61.             CityID = id;
  62.             routes = travel_costs;
  63.         }
  64.  
  65.  
  66.         public override int GetHashCode()
  67.         {
  68.             return CityID.GetHashCode();
  69.         }
  70.  
  71.         public override bool Equals(object obj)
  72.         {
  73.             if (obj is City)
  74.             {
  75.                 return ((City)obj).CityID == this.CityID;
  76.             }
  77.             else return false;
  78.         }
  79.  
  80.         public List<Operator> ApplicableOperators()
  81.         {
  82.             List<Operator> routes = new List<Operator>(this.routes.Count);
  83.             foreach (var route in this.routes)
  84.             {
  85.                 routes.Add(new Travel(CityID, route.Key, route.Value));
  86.             }
  87.             return routes;
  88.         }
  89.  
  90.     }
  91.  
  92.     class Shortest_Path_Problem : Problem
  93.     {
  94.         public static Dictionary<int, Dictionary<int, int>> cities_and_their_neighbours;
  95.         public static int DestinationID { get; private set; }
  96.         private static int StartID { get; set; }
  97.  
  98.         public Shortest_Path_Problem(int start, int destination, Dictionary<int, Dictionary<int, int>> map)
  99.         {
  100.             StartID = start;
  101.             DestinationID = destination;
  102.             cities_and_their_neighbours = map;
  103.         }
  104.  
  105.         public State StartState()
  106.         {
  107.             return new City(StartID, cities_and_their_neighbours[StartID]);
  108.         }
  109.     }
  110.  
  111.     class Optimal_Searcher
  112.     {
  113.  
  114.         Problem p;
  115.  
  116.         public Optimal_Searcher(Problem p)
  117.         {
  118.             this.p = p;
  119.         }
  120.  
  121.  
  122.         private class Node : IEquatable<Node>
  123.         {
  124.  
  125.             internal State state;
  126.  
  127.             internal Operator op;
  128.  
  129.             internal Node parent;
  130.  
  131.             internal int roadExpense;
  132.  
  133.  
  134.  
  135.             public Node(State state, Operator op, Node parent, int expense)
  136.             {
  137.                 this.roadExpense = expense;
  138.                 this.op = op;
  139.                 this.parent = parent;
  140.                 this.state = state;
  141.             }
  142.  
  143.  
  144.             public override string ToString()
  145.             {
  146.                 StringBuilder sb = new StringBuilder();
  147.                 if (op != null) sb.Append("Previous operator: ").Append(op.ToString()).Append('\n');
  148.                 sb.Append(state.ToString()).Append('\n');
  149.                 sb.Append("Road expense = ").Append(roadExpense).Append('\n').Append("\n\n");
  150.                 return sb.ToString();
  151.             }
  152.  
  153.  
  154.             public override bool Equals(Object obj)
  155.             {
  156.                 return ((Node)obj).state.Equals(this.state);
  157.             }
  158.  
  159.             public override int GetHashCode()
  160.             {
  161.                 return state.GetHashCode() + 1;
  162.             }
  163.  
  164.             public bool Equals(Node other)
  165.             {
  166.                 return other.state.Equals(this.state);
  167.             }
  168.  
  169.         }
  170.  
  171.         // Sorted by road expense
  172.         private LinkedList<Node> openNodes;
  173.  
  174.         //private List<Node> closedNodes;
  175.  
  176.         private Node result;
  177.  
  178.         public int Run()
  179.         {
  180.           //  closedNodes = new List<Node>();
  181.             openNodes = new LinkedList<Node>();
  182.             Node start_node = new Node(p.StartState(), null, null, 0);
  183.             openNodes.AddFirst(start_node);
  184.  
  185.             while (true)
  186.             {
  187.                 if (openNodes.Count == 0)
  188.                 {
  189.                     result = null;
  190.                     return -1;
  191.                 }
  192.                 Node node = ChooseMinNode();
  193.                 if (node.state.IsGoal())
  194.                 {
  195.                     result = node;
  196.                     return node.roadExpense;
  197.                 }
  198.                 foreach (Operator op in node.state.ApplicableOperators())
  199.                 {
  200.                     State newState = op.apply(node.state);
  201.                     Node new_node;
  202.                     int newExpense = node.roadExpense + op.Expense(node.state);
  203.  
  204.                     if (newExpense <= 200000)// Max length of any road
  205.                     {
  206.                         Node open_match = search(openNodes, newState);
  207.                         //Node closed_match = search(closedNodes, newState);
  208.  
  209.                         if (open_match == null /*&& closed_match == null*/)
  210.                         {
  211.                             new_node = new Node(newState, op, node, newExpense);
  212.  
  213.                             // Inserting the node in an ordered way.
  214.                             var first_greater = openNodes.First;
  215.  
  216.                             while (first_greater != null && first_greater.Value.roadExpense < new_node.roadExpense)
  217.                                 first_greater = first_greater.Next;
  218.  
  219.                             if (first_greater == null)// All list items are smaller than the new node
  220.                                 openNodes.AddLast(new_node);
  221.                             else
  222.                                 openNodes.AddBefore(first_greater, new_node);
  223.                         }
  224.                         else if (open_match != null)
  225.                         {
  226.                             if (newExpense < open_match.roadExpense)
  227.                             {
  228.                                 open_match.parent = node;
  229.                                 open_match.roadExpense = newExpense;
  230.                                 open_match.op = op;
  231.                             }
  232.                         }
  233.                     }
  234.  
  235.                 }
  236.                 openNodes.Remove(node);
  237.  
  238.  
  239.                 // If we don't yet know a path from the start city to the current city OR the currently known path is greater than the newly built path THEN we save the newly built path.
  240.                 if (!Shortest_Path_Problem.cities_and_their_neighbours[((City)start_node.state).CityID].ContainsKey(((City)node.state).CityID) || Shortest_Path_Problem.cities_and_their_neighbours[((City)start_node.state).CityID][((City)node.state).CityID] > node.roadExpense)
  241.                 {
  242.                     Shortest_Path_Problem.cities_and_their_neighbours[((City)start_node.state).CityID][((City)node.state).CityID] = node.roadExpense;
  243.                     Shortest_Path_Problem.cities_and_their_neighbours[((City)node.state).CityID][((City)start_node.state).CityID] = node.roadExpense;
  244.                     Program.precalculated[new KeyValuePair<int, int>(((City)start_node.state).CityID, ((City)node.state).CityID)] = node.roadExpense;
  245.                     Program.precalculated[new KeyValuePair<int, int>(((City)node.state).CityID, ((City)start_node.state).CityID)] = node.roadExpense;
  246.                 }
  247.             //    closedNodes.Add(node);
  248.             }
  249.  
  250.         }
  251.  
  252.         private Node ChooseMinNode()
  253.         {
  254.             return openNodes.First.Value;
  255.         }
  256.  
  257.         private Node search(IEnumerable<Node> nodeList, State state)
  258.         {
  259.             foreach (Node node in nodeList)
  260.                 if (state.Equals(node.state))
  261.                     return node;
  262.             return null;
  263.         }
  264.  
  265.  
  266.         public ICollection<Operator> getSolution()
  267.         {
  268.             if (result == null)
  269.                 return null;
  270.             LinkedList<Operator> solution = new LinkedList<Operator>();
  271.             Node tmp = result;
  272.             while (tmp.op != null)
  273.             {
  274.                 solution.AddFirst(tmp.op);
  275.                 tmp = tmp.parent;
  276.             }
  277.             return solution;
  278.         }
  279.  
  280.     }
  281.  
  282.  
  283.     class Program
  284.     {
  285.         // Storing already calculated shortest paths
  286.         public static Dictionary<KeyValuePair<int, int>, int> precalculated;
  287.  
  288.         static void Main(string[] args)
  289.         {
  290.             int case_count = int.Parse(Console.ReadLine());
  291.  
  292.             precalculated = new Dictionary<KeyValuePair<int, int>, int>();
  293.  
  294.  
  295.             for (int i = 0; i < case_count; i++)
  296.             {
  297.                 if (i > 0) Console.ReadLine();
  298.                 int cities_count = int.Parse(Console.ReadLine());
  299.  
  300.                 var cities_and_neighbours = new List<int[]>(cities_count);
  301.                 var cities_and_neighbours_costs = new List<int[]>(cities_count);
  302.                 var cities = new List<string>(cities_count);
  303.  
  304.                 for (int j = 0; j < cities_count; j++)
  305.                 {
  306.                     string city = Console.ReadLine();
  307.  
  308.                     int neighbour_count = int.Parse(Console.ReadLine());
  309.  
  310.  
  311.                     cities.Add(city);
  312.                     cities_and_neighbours.Add(new int[neighbour_count]);
  313.                     cities_and_neighbours_costs.Add(new int[neighbour_count]);
  314.  
  315.                     for (int k = 0; k < neighbour_count; k++)
  316.                     {
  317.                         string[] num_strings = Console.ReadLine().Split();
  318.                         cities_and_neighbours[j][k] = int.Parse(num_strings[0]) - 1;
  319.                         cities_and_neighbours_costs[j][k] = int.Parse(num_strings[1]);
  320.  
  321.                     }
  322.                 }
  323.  
  324.  
  325.                 var map = new Dictionary<int, Dictionary<int, int>>();
  326.                 for (int j = 0; j < cities_count; j++)
  327.                 {
  328.                     var routes_from_this_city = new Dictionary<int, int>();
  329.  
  330.                     for (int k = 0; k < cities_and_neighbours[j].Length; k++)
  331.                     {
  332.                         routes_from_this_city.Add(cities_and_neighbours[j][k], cities_and_neighbours_costs[j][k]);
  333.                     }
  334.                     map.Add(j, routes_from_this_city);
  335.                 }
  336.  
  337.                 int route_count;
  338.                 route_count = int.Parse(Console.ReadLine());
  339.                 for (int j = 0; j < route_count; j++)
  340.                 {
  341.                     string[] source_and_dest = Console.ReadLine().Split();
  342.                     int source_index = cities.IndexOf(source_and_dest[0]), destination_index = cities.IndexOf(source_and_dest[1]);
  343.                     int min_cost;
  344.  
  345.                     if (!precalculated.ContainsKey(new KeyValuePair<int, int>(source_index, destination_index)))
  346.                     {
  347.                         var problem = new Shortest_Path_Problem(source_index, destination_index, map);
  348.                         var solver = new Optimal_Searcher(problem);
  349.  
  350.                         min_cost = solver.Run();
  351.                         // saving results
  352.                         map[source_index][destination_index] = min_cost;
  353.                         map[destination_index][source_index] = min_cost;
  354.                         precalculated[new KeyValuePair<int, int>(source_index, destination_index)] = min_cost;
  355.                         precalculated[new KeyValuePair<int, int>(destination_index, source_index)] = min_cost;
  356.                     }
  357.                     else
  358.                         min_cost = precalculated[new KeyValuePair<int, int>(source_index, destination_index)];
  359.                     Console.WriteLine(min_cost);
  360.                 }
  361.             }
  362.  
  363.         }
  364.     }
  365. }
Advertisement
RAW Paste Data Copied
Advertisement