sA1monxGod

Untitled

Jun 8th, 2021
941
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using Contest;
  2. using System;
  3. using System.Collections.Generic;
  4. using System.IO;
  5. using System.Linq;
  6.  
  7. namespace Contest
  8. {
  9.     internal class Edge
  10.     {
  11.         public int From { get; set; }
  12.         public int To { get; set; }
  13.         public int Cost { get; set; }
  14.  
  15.         public Edge(int @from, int to, int cost)
  16.         {
  17.             From = @from;
  18.             To = to;
  19.             Cost = cost;
  20.         }
  21.     }
  22.  
  23.     internal class Graph
  24.     {
  25.         private int _n;
  26.         private int _m;
  27.         private List<Edge> _edges;
  28.  
  29.         public Graph(int n, int m)
  30.         {
  31.             _n = n;
  32.             _m = m;
  33.             _edges = new List<Edge>();
  34.         }
  35.  
  36.         private static List<double> FillDoubleList(int count, double value = 0)
  37.         {
  38.             var result = new List<double>(count);
  39.  
  40.             for (var i = 0; i < count; i++)
  41.             {
  42.                 result.Add(value);
  43.             }
  44.  
  45.             return result;
  46.         }
  47.  
  48.         public void Add(Edge edge)
  49.         {
  50.             _edges.Add(edge);
  51.             _edges.Add(new Edge(edge.To, edge.From, edge.Cost));
  52.         }
  53.  
  54.         public double GetShortestWayProbability(int @from, int to)
  55.         {
  56.             var distance = FillDoubleList(_n, double.MaxValue);
  57.             distance[@from] = 0d;
  58.  
  59.             var used = new bool[_n];
  60.             for (var i = 0; i < _n; i++)
  61.             {
  62.                 var v = -1;
  63.                 for (var j = 0; j < _n; j++)
  64.                     if (!used[j] && (v == -1 || distance[j] < distance[v]))
  65.                         v = j;
  66.                 if (Math.Abs(distance[v] - double.MaxValue) < 1e-9)
  67.                     break;
  68.  
  69.                 used[v] = true;
  70.  
  71.                 foreach (var edge in _edges.Where(e => e.From == v))
  72.                 {
  73.                     if (distance[v] + (edge.Cost / 100.0) * (1 - distance[v]) < distance[edge.To])
  74.                     {
  75.                         distance[edge.To] = distance[v] + (edge.Cost / 100.0) * (1 - distance[v]);
  76.                     }
  77.                 }
  78.             }
  79.  
  80.             return distance[to];
  81.         }
  82.     }
  83. }
  84.  
  85. internal class Program
  86. {
  87.  
  88.     private static void Main()
  89.     {
  90.         var sr = new StreamReader("input.txt");
  91.         var args = sr.ReadLine()
  92.             .Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries)
  93.             .Select(int.Parse)
  94.             .ToArray();
  95.  
  96.         int n = args[0], m = args[1];
  97.         var graph = new Graph(n, m);
  98.  
  99.         args = sr.ReadLine()
  100.             .Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries)
  101.             .Select(int.Parse)
  102.             .ToArray();
  103.  
  104.         int f = args[0] - 1, t = args[1] - 1;
  105.  
  106.         for (var i = 0; i < m; i++)
  107.         {
  108.             args = sr.ReadLine()
  109.                 .Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries)
  110.                 .Select(int.Parse)
  111.                 .ToArray();
  112.  
  113.             var edge = new Edge(args[0] - 1, args[1] - 1, args[2]);
  114.             graph.Add(edge);
  115.         }
  116.  
  117.         sr.Close();
  118.         var probability = graph.GetShortestWayProbability(f, t);
  119.  
  120.         using (var sw = new StreamWriter("output.txt"))
  121.         {
  122.             sw.WriteLine(Math.Round(probability, 8));
  123.         }
  124.     }
  125. }
RAW Paste Data