MostReliablePath

using System;
using System.Collections.Generic;
using System.Linq;
using Wintellect.PowerCollections;

namespace MostReliablePath
{
    class Program
    {
        private class Edge
        {
            public int First { get; set; }

            public int Second { get; set; }

            public int Weight { get; set; }

            public override string ToString()
            {
                return $"{this.First} - {this.Second}";
            }
        }

        static void Main(string[] args)
        {
            int nodesCount = int.Parse(Console.ReadLine());
            int edgesCount = int.Parse(Console.ReadLine());
            List<Edge>[] graph = ReadGraph(nodesCount, edgesCount);
            int start = int.Parse(Console.ReadLine());
            int end = int.Parse(Console.ReadLine());

            GetMostReliablePath(graph, start, end);
        }

        private static void GetMostReliablePath(List<Edge>[] graph, int start, int end)
        {
            double[] distances = new double[graph.Length];
            for (int i = 0; i < distances.Length; i++)
            {
                distances[i] = double.NegativeInfinity;
            }
            //Array.Fill(distances, double.NegativeInfinity);
            distances[start] = 100;

            int[] previous = new int[graph.Length];
            previous[start] = -1;

            bool[] visited = new bool[graph.Length];

            OrderedBag<int> queue = new OrderedBag<int>(
                Comparer<int>.Create((a, b) => distances[b].CompareTo(distances[a])));

            queue.Add(start);
            visited[start] = true;

            while (queue.Count > 0)
            {
                int nearestNode = queue.RemoveFirst();

                if (nearestNode == end)
                {
                    Stack<int> path = ReconstructPath(previous, end);

                    Console.WriteLine($"Most reliable path reliability: {distances[nearestNode]:f2}%");
                    Console.WriteLine(string.Join(" -> ", path));

                    break;
                }

                foreach (Edge edge in graph[nearestNode])
                {
                    int childNode = edge.Second;

                    if (!visited[childNode])
                    {
                        queue.Add(childNode);
                        visited[childNode] = true;
                    }

                    double newDistance = (edge.Weight * distances[nearestNode]) / 100;
                    if (newDistance > distances[childNode])
                    {
                        distances[childNode] = newDistance;
                        previous[childNode] = nearestNode;

                        queue = new OrderedBag<int>(
                            queue,
                            Comparer<int>.Create((a, b) => distances[b].CompareTo(distances[a])));
                    }
                }
            }
        }

        private static Stack<int> ReconstructPath(int[] previous, int node)
        {
            Stack<int> path = new Stack<int>();

            while (node != -1)
            {
                path.Push(node);
                node = previous[node];
            }

            return path;
        }

        private static List<Edge>[] ReadGraph(int nodesCount, int edgesCount)
        {
            List<Edge>[] graph = new List<Edge>[nodesCount];

            for (int i = 0; i < graph.Length; i++)
            {
                graph[i] = new List<Edge>();
            }

            for (int i = 0; i < edgesCount; i++)
            {
                int[] data = Console.ReadLine()
                    .Split()
                    .Select(int.Parse)
                    .ToArray();
                int first = data[0];
                int second = data[1];
                int weight = data[2];

                graph[first].Add(new Edge
                {
                    First = first,
                    Second = second,
                    Weight = weight,
                });

                graph[second].Add(new Edge
                {
                    First = second,
                    Second = first,
                    Weight = weight,
                });
            }

            return graph;
        }
    }
}