using System;

using System.Linq;

using System.Collections.Generic;

using ConcurrentPriorityQueue;

​

public struct Distance<T> {

    public int Value;

    public T Node;

}

​

public class Program

{   

    public class Graph<T> where T: IComparable<T> {

        private readonly Dictionary<T, List<Edge>> _adj;

        public Graph() {

            _adj = new Dictionary<T, List<Edge>>();

        }

        public void AddEdge(T source) {

            _adj[source] = new List<Edge>();

        }

        public void AddEdge(T source, T dest, int weight) {

            List<Edge> verticies;

            if(!_adj.TryGetValue(source, out verticies)) {

                verticies = new List<Edge>();

            }

            verticies.Add(new Edge(dest, weight));

            _adj[source] = verticies;

        }

        public Dictionary<T, T> PrimMinimalSpanningTree(T start) {

            var q = new ConcurrentPriorityQueue<T, int>();

            q.Enqueue(start, 0);

            var dist = new Dictionary<T, int>();

            var path = new Dictionary<T, T>();

            var visited = new HashSet<T>();

            foreach(var n in _adj.Keys) {

                dist[n] = int.MaxValue;

            }

            dist[start] = 0;

            q.Enqueue(start, 0);

            while(q.Count() > 0) {

                var cur = q.Dequeue();

                visited.Add(cur);

                foreach(var edge in _adj[cur]) {

                    //Console.WriteLine("from={0} {1}", cur, edge, dist[cur]);

                    if(visited.Contains(edge.Node)) {

                        continue;

                    }

                    var newDist = edge.Weight;

                    if(newDist < dist[edge.Node]) {

                        //it's invalid we should check if it's in Queue, if it is, decrease key

                        q.Enqueue(edge.Node, newDist);

                        dist[edge.Node] = newDist;

                        path[edge.Node] = cur;

                    }

                }

            }

            Console.WriteLine("dist=[{0}]", string.Join(",", dist));

            //Console.WriteLine("path=[{0}]", string.Join(",", path));

            return path;

        }

        private class Edge {

            public readonly T Node;

            public readonly int Weight;

            public Edge(T node, int weight) {

                Node = node;

                Weight = weight;

            }

            public override string ToString() {

                return string.Format("To={0} Weight={1}", Node, Weight);

            }

        }

    }

    public static void Main()

    {

        var graph = new Graph<int>();

        graph.AddEdge(0, 1, 4);

        graph.AddEdge(0, 7, 8);

        graph.AddEdge(1, 2, 8);

        graph.AddEdge(1, 7, 11);

        graph.AddEdge(2, 3, 7);

        graph.AddEdge(2, 8, 2);

        graph.AddEdge(2, 5, 4);

        graph.AddEdge(3, 4, 9);

        graph.AddEdge(3, 5, 14);

        graph.AddEdge(4, 5, 10);

        graph.AddEdge(5, 6, 2);

        graph.AddEdge(6, 7, 1);

        graph.AddEdge(6, 8, 6);

        graph.AddEdge(7, 8, 7);

        graph.AddEdge(8);

        Console.WriteLine("MinimalSpanningTree: {0}", string.Join("->", graph.PrimMinimalSpanningTree(0)));

    }

}