Graphs (from Friends in need)

namespace Graphs
{
    using System;
    using System.Collections;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;

    public class Program
    {
        private static readonly HashSet<int> hospitals = new HashSet<int>();
        private static readonly Graph<int> graph = new Graph<int>();

        /// <summary>
        /// Friends in Need
        /// On the first line will be read three integer numbers N, M and H (separated by a single white space), that represent corresponding the number of points on the map (both hospitals and homes), the number of streets between points and the number of hospitals.
        /// On the second line will be H integer numbers, the points on the map that are hospitals. All the rest of the points are homes.
        /// On the next M lines will be the streets. Each line contains three positive integer numbers F, S and D. That means that there is a street between points F and S, and the distance between them is D. All the streets are directional, i.e. if a street from A to B exists, there is a street from B to A.
        /// 3 2 1
        /// 1
        /// 1 2 1
        /// 3 2 2
        /// Output: 4
        /// </summary>
        /// <param name="args"></param>
        static void Main(string[] args)
        {
            string[] buffer = Console.ReadLine().Split(' ');
            int n = int.Parse(buffer[0]);
            int m = int.Parse(buffer[1]);
            int h = int.Parse(buffer[2]);
            buffer = Console.ReadLine().Split(' ');
            int nodeName;
            for (int i = 0; i < h; i++)
            {
                nodeName = int.Parse(buffer[i]);
                hospitals.Add(nodeName);
                graph.AddNode(nodeName);
            }

            for (int i = 0; i < m; i++)
            {
                buffer = Console.ReadLine().Split(' ');
                graph.AddConnection(int.Parse(buffer[0]), int.Parse(buffer[1]), int.Parse(buffer[2]), true);
            }

            int sumDistance = int.MaxValue;
            foreach (var hospital in hospitals)
            {
                List<Node<int>> nodes = graph.FindShortestDistanceToAllNodes(hospital);
                int currentDistance = 0;
                foreach (var node in nodes)
                {
                    if (!hospitals.Contains(node.Name))
                    {
                        currentDistance += (int)node.DijkstraDistance;
                    }
                }

                if (currentDistance < sumDistance)
                {
                    sumDistance = currentDistance;
                }
            }

            Console.WriteLine(sumDistance);
        }
    }

    public class Graph<T>
    {
        internal IDictionary<T, Node<T>> Nodes { get; private set; }

        private readonly HashSet<Node<T>> visited;

        public Graph()
        {
            Nodes = new Dictionary<T, Node<T>>();
            visited = new HashSet<Node<T>>();
        }

        public void AddNode(T name)
        {
            var node = new Node<T>(name);
            if (Nodes.ContainsKey(name))
            {
                throw new ArgumentException(string.Format("Node with name {0} is existing in the graph.", name));
            }
            Nodes.Add(name, node);
        }

        public void AddConnection(T fromNode, T toNode, int distance, bool twoWay)
        {
            if (!Nodes.ContainsKey(fromNode))
            {
                this.AddNode(fromNode);
            }

            if (!Nodes.ContainsKey(toNode))
            {
                this.AddNode(toNode);
            }

            Nodes[fromNode].AddConnection(Nodes[toNode], distance, twoWay);
        }

        public List<Node<T>> FindShortestDistanceToAllNodes(T startNodeName)
        {
            if (!Nodes.ContainsKey(startNodeName))
            {
                throw new ArgumentOutOfRangeException(string.Format("{0} is not containing in the graph.", startNodeName));
            }

            SetShortestDistances(Nodes[startNodeName]);
            List<Node<T>> nodes = new List<Node<T>>();
            foreach (var item in Nodes)
            {
                if (!item.Key.Equals(startNodeName))
                {
                    nodes.Add(item.Value);
                }
            }
            return nodes;
        }

        private void SetShortestDistances(Node<T> startNode)
        {
            PriorityQueue<Node<T>> queue = new PriorityQueue<Node<T>>();

            // set to all nodes DijkstraDistance to PositiveInfinity
            foreach (var node in Nodes)
            {
                if (!startNode.Name.Equals(node.Key))
                {
                    node.Value.DijkstraDistance = double.PositiveInfinity;
                    //queue.Enqueue(node.Value);
                }
            }

            startNode.DijkstraDistance = 0.0d;
            queue.Enqueue(startNode);

            while (queue.Count != 0)
            {
                Node<T> currentNode = queue.Dequeue();

                if (currentNode.DijkstraDistance == double.PositiveInfinity)
                {
                    break;
                }

                foreach (var neighbour in Nodes[currentNode.Name].Connections)
                {
                    double subDistance = currentNode.DijkstraDistance + neighbour.Distance;

                    if (subDistance < neighbour.To.DijkstraDistance)
                    {
                        neighbour.To.DijkstraDistance = subDistance;
                        queue.Enqueue(neighbour.To);
                    }
                }
            }
        }

        public void SetAllDijkstraDistanceValue(double value)
        {
            foreach (var node in Nodes)
            {
                node.Value.DijkstraDistance = value;
            }
        }

        public double GetSumOfAllDijkstraDistance()
        {
            foreach (var item in Nodes)
            {
                if (!visited.Contains(item.Value))
                {
                    EmployDfs(item.Value);
                }
            }
            double sum = 0;
            foreach (var node in Nodes)
            {
                sum += node.Value.DijkstraDistance;
            }

            return sum;
        }

        public void EmployDfs(Node<T> node)
        {
            visited.Add(node);
            foreach (var item in node.Connections)
            {
                if (!visited.Contains(item.To))
                {
                    EmployDfs(item.To);
                }
                node.DijkstraDistance += item.To.DijkstraDistance;
            }

            if (node.DijkstraDistance == 0)
            {
                node.DijkstraDistance++;
            }
        }

        public void EmployBfs(T nodeName)
        {
            Queue<Node<T>> nodes = new Queue<Node<T>>();
            Node<T> node = Nodes[nodeName];
            nodes.Enqueue(node);
            while (nodes.Count != 0)
            {
                Node<T> currentNode = nodes.Dequeue();
                currentNode.DijkstraDistance++;

                foreach (var connection in Nodes[currentNode.Name].Connections)
                {
                    nodes.Enqueue(connection.To);
                }
            }
        }

        public List<Edge<T>> PrimeMinimumSpanningTree(T startNodeName)
        {
            if (!Nodes.ContainsKey(startNodeName))
            {
                throw new ArgumentOutOfRangeException(string.Format("{0} is not containing in the graph.", startNodeName));
            }

            List<Edge<T>> mpdTree = new List<Edge<T>>();
            PriorityQueue<Edge<T>> queue = new PriorityQueue<Edge<T>>();
            Node<T> node = Nodes[startNodeName];
            foreach (var edge in node.Connections)
            {
                queue.Enqueue(edge);
            }

            visited.Add(node);

            while (queue.Count > 0)
            {
                Edge<T> edge = queue.Dequeue();

                if (!visited.Contains(edge.To))
                {
                    node = edge.To;
                    visited.Add(node); //we "visit" this node
                    mpdTree.Add(edge);
                    foreach (var item in node.Connections)
                    {
                        if (!mpdTree.Contains(item))
                        {
                            if (!visited.Contains(item.To))
                            {
                                queue.Enqueue(item);
                            }
                        }
                    }
                }
            }
            visited.Clear();
            return mpdTree;
        }

        public override string ToString()
        {
            StringBuilder result = new StringBuilder();

            foreach (var node in this.Nodes)
            {
                result.Append(node.Key + " -> ");

                foreach (var conection in node.Value.Connections)
                {
                    result.Append(conection.To + "-" + conection.Distance + " ");
                }

                result.AppendLine();
            }

            return result.ToString();
        }
    }

    public class Node<T> : IComparable
    {
        private readonly IList<Edge<T>> connectionsList;

        public T Name { get; private set; }

        public double DijkstraDistance { get; set; }

        public List<Node<T>> DijkstraPath { get; set; }

        internal IEnumerable<Edge<T>> Connections
        {
            get
            {
                return connectionsList;
            }
        }

        public Node(T name)
        {
            Name = name;
            connectionsList = new List<Edge<T>>();
        }

        internal void AddConnection(Node<T> targetNode, double distance, bool twoWay)
        {
            if (targetNode == null)
            {
                throw new ArgumentNullException("targetNode");
            }

            if (targetNode == this)
            {
                throw new ArgumentException("Node may not connect to itself.");
            }

            if (distance < 0)
            {
                throw new ArgumentException("Distance must be positive.");
            }

            connectionsList.Add(new Edge<T>(this, targetNode, distance));
            if (twoWay)
            {
                targetNode.AddConnection(this, distance, false);
            }
        }

        public override string ToString()
        {
            return this.Name.ToString();
        }

        public int CompareTo(object obj)
        {
            return this.DijkstraDistance.CompareTo((obj as Node<T>).DijkstraDistance);
        }
    }

    public class Edge<T> : IComparable
    {
        internal Node<T> From { get; private set; }

        internal Node<T> To { get; private set; }

        internal double Distance { get; private set; }

        internal Edge(Node<T> from, Node<T> to, double distance)
        {
            this.From = from;
            this.To = to;
            this.Distance = distance;
        }

        public int CompareTo(object obj)
        {
            return this.Distance.CompareTo((obj as Edge<T>).Distance);
        }

        public override string ToString()
        {
            return string.Format("({0} {1}) -> {2}", From, To, Distance);
        }
    }

    public class PriorityQueue<T> : IEnumerable
        where T : IComparable
    {
        private readonly List<T> heap;

        public PriorityQueue()
        {
            heap = new List<T>();
        }

        public PriorityQueue(int size)
        {
            heap = new List<T>(size);
        }

        public int Count
        {
            get
            {
                return this.heap.Count;
            }
        }

        public bool IsEmpty
        {
            get
            {
                return this.heap.Count == 0;
            }
        }

        public void Enqueue(T item)
        {
            this.heap.Add(item);

            int childIndex = this.heap.Count - 1;
            while (childIndex > 0)
            {
                int parentIndex = (childIndex - 1) / 2;
                if (this.heap[parentIndex].CompareTo(this.heap[childIndex]) <= 0)
                {
                    break;
                }

                T swap = this.heap[childIndex];
                this.heap[childIndex] = this.heap[parentIndex];
                this.heap[parentIndex] = swap;

                childIndex = parentIndex;
            }
        }

        public T Dequeue()
        {
            if (this.heap.Count == 0)
            {
                throw new InvalidOperationException("Queue empty.");
            }

            int lastIndex = this.heap.Count - 1;

            T topItem = this.heap[0];
            this.heap[0] = this.heap[lastIndex];
            this.heap.RemoveAt(lastIndex);
            lastIndex--;

            int parentIndex = 0;
            while (true)
            {
                int leftIndex = 2 * parentIndex + 1;
                if (leftIndex > lastIndex)
                {
                    break;
                }

                int swapIndex = leftIndex;
                int rightIndex = leftIndex + 1;
                if (rightIndex <= lastIndex && this.heap[rightIndex].CompareTo(this.heap[leftIndex]) < 0)
                {
                    swapIndex = rightIndex;
                }

                if (this.heap[parentIndex].CompareTo(this.heap[swapIndex]) <= 0)
                {
                    // the parent and the child are in order
                    break;
                }

                T swap = this.heap[swapIndex];
                this.heap[swapIndex] = this.heap[parentIndex];
                this.heap[parentIndex] = swap;

                parentIndex = swapIndex;
            }

            return topItem;
        }

        public T Peek()
        {
            if (this.heap.Count == 0)
            {
                throw new InvalidOperationException("Queue empty.");
            }

            T topItem = this.heap[0];
            return topItem;
        }

        public void Clear()
        {
            this.heap.Clear();
        }

        public IEnumerator<T> GetEnumerator()
        {
            return this.heap.GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }

        public T[] ToArray()
        {
            return this.heap.ToArray();
        }

        public override string ToString()
        {
            return string.Join(", ", this.heap);
        }
    }
}