TSHPATH in SPOJ

using System;
using System.Collections.Generic;
using System.Text;

namespace Turtles_shortest_path
{
    interface Operator
    {
        State apply(State s);
        int Expense(State s);
    }

    interface State
    {
        List<Operator> ApplicableOperators();
        bool IsGoal();
    }

    interface Problem
    {
        State StartState();
    }


    class Travel : Operator
    {
        public int From { get; private set; }
        public int To { get; private set; }
        public int Cost { get; private set; }

        public Travel(int from, int to, int cost)
        {
            From = from;
            To = to;
            Cost = cost;
        }
        public State apply(State s)
        {
            return new City(To, Shortest_Path_Problem.cities_and_their_neighbours[To]);
        }


        public int Expense(State s)
        {
            return Cost;
        }
    }

    class City : State
    {
        private Dictionary<int, int> routes;
        public int CityID { get; set; }
        public bool IsGoal()
        {
            return this.CityID == Shortest_Path_Problem.DestinationID;
        }


        public City(int id, Dictionary<int, int> travel_costs)
        {
            CityID = id;
            routes = travel_costs;
        }


        public override int GetHashCode()
        {
            return CityID.GetHashCode();
        }

        public override bool Equals(object obj)
        {
            if (obj is City)
            {
                return ((City)obj).CityID == this.CityID;
            }
            else return false;
        }

        public List<Operator> ApplicableOperators()
        {
            List<Operator> routes = new List<Operator>(this.routes.Count);
            foreach (var route in this.routes)
            {
                routes.Add(new Travel(CityID, route.Key, route.Value));
            }
            return routes;
        }

    }

    class Shortest_Path_Problem : Problem
    {
        public static Dictionary<int, Dictionary<int, int>> cities_and_their_neighbours;
        public static int DestinationID { get; private set; }
        private static int StartID { get; set; }

        public Shortest_Path_Problem(int start, int destination, Dictionary<int, Dictionary<int, int>> map)
        {
            StartID = start;
            DestinationID = destination;
            cities_and_their_neighbours = map;
        }

        public State StartState()
        {
            return new City(StartID, cities_and_their_neighbours[StartID]);
        }
    }

    class Optimal_Searcher
    {

        Problem p;

        public Optimal_Searcher(Problem p)
        {
            this.p = p;
        }


        private class Node : IEquatable<Node>
        {

            internal State state;

            internal Operator op;

            internal Node parent;

            internal int roadExpense;



            public Node(State state, Operator op, Node parent, int expense)
            {
                this.roadExpense = expense;
                this.op = op;
                this.parent = parent;
                this.state = state;
            }


            public override string ToString()
            {
                StringBuilder sb = new StringBuilder();
                if (op != null) sb.Append("Previous operator: ").Append(op.ToString()).Append('\n');
                sb.Append(state.ToString()).Append('\n');
                sb.Append("Road expense = ").Append(roadExpense).Append('\n').Append("\n\n");
                return sb.ToString();
            }


            public override bool Equals(Object obj)
            {
                return ((Node)obj).state.Equals(this.state);
            }

            public override int GetHashCode()
            {
                return state.GetHashCode() + 1;
            }

            public bool Equals(Node other)
            {
                return other.state.Equals(this.state);
            }

        }

        // Sorted by road expense
        private LinkedList<Node> openNodes;

        //private List<Node> closedNodes;

        private Node result;

        public int Run()
        {
          //  closedNodes = new List<Node>();
            openNodes = new LinkedList<Node>();
            Node start_node = new Node(p.StartState(), null, null, 0);
            openNodes.AddFirst(start_node);

            while (true)
            {
                if (openNodes.Count == 0)
                {
                    result = null;
                    return -1;
                }
                Node node = ChooseMinNode();
                if (node.state.IsGoal())
                {
                    result = node;
                    return node.roadExpense;
                }
                foreach (Operator op in node.state.ApplicableOperators())
                {
                    State newState = op.apply(node.state);
                    Node new_node;
                    int newExpense = node.roadExpense + op.Expense(node.state);

                    if (newExpense <= 200000)// Max length of any road
                    {
                        Node open_match = search(openNodes, newState);
                        //Node closed_match = search(closedNodes, newState);

                        if (open_match == null /*&& closed_match == null*/)
                        {
                            new_node = new Node(newState, op, node, newExpense);

                            // Inserting the node in an ordered way.
                            var first_greater = openNodes.First;

                            while (first_greater != null && first_greater.Value.roadExpense < new_node.roadExpense)
                                first_greater = first_greater.Next;

                            if (first_greater == null)// All list items are smaller than the new node
                                openNodes.AddLast(new_node);
                            else
                                openNodes.AddBefore(first_greater, new_node);
                        }
                        else if (open_match != null)
                        {
                            if (newExpense < open_match.roadExpense)
                            {
                                open_match.parent = node;
                                open_match.roadExpense = newExpense;
                                open_match.op = op;
                            }
                        }
                    }

                }
                openNodes.Remove(node);


                // 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.
                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)
                {
                    Shortest_Path_Problem.cities_and_their_neighbours[((City)start_node.state).CityID][((City)node.state).CityID] = node.roadExpense;
                    Shortest_Path_Problem.cities_and_their_neighbours[((City)node.state).CityID][((City)start_node.state).CityID] = node.roadExpense;
                    Program.precalculated[new KeyValuePair<int, int>(((City)start_node.state).CityID, ((City)node.state).CityID)] = node.roadExpense;
                    Program.precalculated[new KeyValuePair<int, int>(((City)node.state).CityID, ((City)start_node.state).CityID)] = node.roadExpense;
                }
            //    closedNodes.Add(node);
            }

        }

        private Node ChooseMinNode()
        {
            return openNodes.First.Value;
        }

        private Node search(IEnumerable<Node> nodeList, State state)
        {
            foreach (Node node in nodeList)
                if (state.Equals(node.state))
                    return node;
            return null;
        }


        public ICollection<Operator> getSolution()
        {
            if (result == null)
                return null;
            LinkedList<Operator> solution = new LinkedList<Operator>();
            Node tmp = result;
            while (tmp.op != null)
            {
                solution.AddFirst(tmp.op);
                tmp = tmp.parent;
            }
            return solution;
        }

    }


    class Program
    {
        // Storing already calculated shortest paths
        public static Dictionary<KeyValuePair<int, int>, int> precalculated;

        static void Main(string[] args)
        {
            int case_count = int.Parse(Console.ReadLine());

            precalculated = new Dictionary<KeyValuePair<int, int>, int>();


            for (int i = 0; i < case_count; i++)
            {
                if (i > 0) Console.ReadLine();
                int cities_count = int.Parse(Console.ReadLine());

                var cities_and_neighbours = new List<int[]>(cities_count);
                var cities_and_neighbours_costs = new List<int[]>(cities_count);
                var cities = new List<string>(cities_count);

                for (int j = 0; j < cities_count; j++)
                {
                    string city = Console.ReadLine();

                    int neighbour_count = int.Parse(Console.ReadLine());


                    cities.Add(city);
                    cities_and_neighbours.Add(new int[neighbour_count]);
                    cities_and_neighbours_costs.Add(new int[neighbour_count]);

                    for (int k = 0; k < neighbour_count; k++)
                    {
                        string[] num_strings = Console.ReadLine().Split();
                        cities_and_neighbours[j][k] = int.Parse(num_strings[0]) - 1;
                        cities_and_neighbours_costs[j][k] = int.Parse(num_strings[1]);

                    }
                }


                var map = new Dictionary<int, Dictionary<int, int>>();
                for (int j = 0; j < cities_count; j++)
                {
                    var routes_from_this_city = new Dictionary<int, int>();

                    for (int k = 0; k < cities_and_neighbours[j].Length; k++)
                    {
                        routes_from_this_city.Add(cities_and_neighbours[j][k], cities_and_neighbours_costs[j][k]);
                    }
                    map.Add(j, routes_from_this_city);
                }

                int route_count;
                route_count = int.Parse(Console.ReadLine());
                for (int j = 0; j < route_count; j++)
                {
                    string[] source_and_dest = Console.ReadLine().Split();
                    int source_index = cities.IndexOf(source_and_dest[0]), destination_index = cities.IndexOf(source_and_dest[1]);
                    int min_cost;

                    if (!precalculated.ContainsKey(new KeyValuePair<int, int>(source_index, destination_index)))
                    {
                        var problem = new Shortest_Path_Problem(source_index, destination_index, map);
                        var solver = new Optimal_Searcher(problem);

                        min_cost = solver.Run();
                        // saving results
                        map[source_index][destination_index] = min_cost;
                        map[destination_index][source_index] = min_cost;
                        precalculated[new KeyValuePair<int, int>(source_index, destination_index)] = min_cost;
                        precalculated[new KeyValuePair<int, int>(destination_index, source_index)] = min_cost;
                    }
                    else
                        min_cost = precalculated[new KeyValuePair<int, int>(source_index, destination_index)];
                    Console.WriteLine(min_cost);
                }
            }

        }
    }
}