Advertisement
Guest User

Untitled

a guest
May 27th, 2016
53
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.20 KB | None | 0 0
  1. using System;
  2. using System.Collections.Generic;
  3. using System.IO;
  4. using System.Linq;
  5. using System.Text;
  6. using System.Threading.Tasks;
  7.  
  8. namespace Dijkstra
  9. {
  10. public class DijkstraData
  11. {
  12. public Node Previous { get; set; }
  13. public double Price { get; set; }
  14. }
  15.  
  16. public class Program
  17. {
  18. public static Tuple<double, List<Node>> Dijkstra(Graph graph, Dictionary<Edge, double> weights, Node start, Node end)
  19. {
  20. var notVisited = graph.Nodes.ToList();
  21. var track = new Dictionary<Node, DijkstraData>();
  22. track.Add(start, new DijkstraData() { Price = 1, Previous = null });
  23.  
  24. while (true)
  25. {
  26. Node toOpen = null;
  27. var bestPrice = double.PositiveInfinity;
  28. foreach (var e in notVisited)
  29. {
  30. if (track.ContainsKey(e) && track[e].Price < bestPrice)
  31. {
  32. bestPrice = track[e].Price;
  33. toOpen = e;
  34. }
  35. }
  36.  
  37. if (toOpen == (null)) return null;
  38. if (toOpen.Equals(end)) break;
  39.  
  40. foreach (var e in toOpen.IncidentEdges.Where(z => z.From.Equals(toOpen)))
  41. {
  42. var currentPrice = track[toOpen].Price * weights[e];
  43. var nextNode = e.OtherNode(toOpen);
  44. if (!track.ContainsKey(nextNode) || track[nextNode].Price > currentPrice)
  45. {
  46. track[nextNode] = new DijkstraData { Previous = toOpen, Price = currentPrice };
  47. }
  48. }
  49.  
  50. notVisited.Remove(toOpen);
  51. }
  52.  
  53. var result = new List<Node>();
  54. var weight = track[end].Price;
  55. while (end != null)
  56. {
  57. result.Add(end);
  58. end = track[end].Previous;
  59. }
  60. result.Reverse();
  61. return Tuple.Create(weight, result);
  62. }
  63. public static void Main()
  64. {
  65. var tuple = ReadInput();
  66. var resultTuple = Dijkstra(tuple.Item1, tuple.Item2, tuple.Item3, tuple.Item4);
  67. WriteOut(resultTuple);
  68. }
  69.  
  70. public static Tuple<Graph, Dictionary<Edge, double>, Node, Node> ReadInput()
  71. {
  72. Graph graph = null;
  73. var weight = new Dictionary<Edge, double>();
  74. Node start = null;
  75. Node end = null;
  76. using (var stream = new StreamReader("in.txt"))
  77. {
  78. var nodeNumber = int.Parse(stream.ReadLine());
  79. var currNode = 0;
  80. graph = new Graph(nodeNumber);
  81. while (currNode < nodeNumber)
  82. {
  83. var str = stream.ReadLine();
  84. var splitted = str.Split(' ');
  85. for (var j = 0; j < splitted.Length - 1; j ++)
  86. {
  87. weight.Add(graph.Connect(currNode, j), Convert.ToDouble(splitted[j]));
  88. }
  89. currNode++;
  90.  
  91. }
  92. start = new Node(int.Parse(stream.ReadLine()) - 1);
  93. end = new Node(int.Parse(stream.ReadLine()) - 1);
  94. }
  95. return Tuple.Create(graph, weight, start, end);
  96.  
  97. }
  98.  
  99. public static void WriteOut(Tuple<double, List<Node>> resultTuple)
  100. {
  101. var result = new List<string>();
  102. if (resultTuple == null)
  103. File.WriteAllText("out.txt", "N");
  104. else
  105. {
  106. result.Add("Y");
  107. var str = new StringBuilder();
  108. foreach (var e in resultTuple.Item2)
  109. {
  110. str.Append(e.NodeNumber + 1);
  111. str.Append(" ");
  112. }
  113. result.Add(str.ToString());
  114. result.Add(resultTuple.Item1.ToString());
  115. File.WriteAllLines("out.txt", result);
  116. }
  117. }
  118. }
  119.  
  120. public class Edge
  121. {
  122. public readonly Node From;
  123. public readonly Node To;
  124. public Edge(Node first, Node second)
  125. {
  126. this.From = first;
  127. this.To = second;
  128. }
  129. public bool IsIncident(Node node)
  130. {
  131. return From == node || To == node;
  132. }
  133. public Node OtherNode(Node node)
  134. {
  135. if (!IsIncident(node)) throw new ArgumentException();
  136. if (From == node) return To;
  137. return From;
  138. }
  139. }
  140.  
  141. public class Node
  142. {
  143. private readonly List<Edge> edges = new List<Edge>();
  144. public readonly int NodeNumber;
  145.  
  146. public Node(int number)
  147. {
  148. NodeNumber = number;
  149. }
  150.  
  151. public IEnumerable<Node> IncidentNodes
  152. {
  153. get { return edges.Select(z => z.OtherNode(this)); }
  154. }
  155.  
  156. public IEnumerable<Edge> IncidentEdges
  157. {
  158. get { foreach (var e in edges) yield return e; }
  159. }
  160.  
  161. public static Edge Connect(Node node1, Node node2, Graph graph)
  162. {
  163. if (!graph.Nodes.Contains(node1) || !graph.Nodes.Contains(node2)) throw new ArgumentException();
  164. var edge = new Edge(node1, node2);
  165. node1.edges.Add(edge);
  166. node2.edges.Add(edge);
  167. return edge;
  168. }
  169.  
  170. public static void Disconnect(Edge edge)
  171. {
  172. edge.From.edges.Remove(edge);
  173. edge.To.edges.Remove(edge);
  174. }
  175.  
  176. public override bool Equals(object obj)
  177. {
  178. if (obj is Node)
  179. {
  180. var node = (Node)obj;
  181. return node.NodeNumber == NodeNumber;
  182. }
  183. return false;
  184. }
  185.  
  186. public override int GetHashCode()
  187. {
  188. return NodeNumber.GetHashCode();
  189. }
  190. }
  191.  
  192. public class Graph
  193. {
  194. private Node[] nodes;
  195.  
  196. public Graph(int nodesCount)
  197. {
  198. nodes = Enumerable.Range(0, nodesCount).Select(z => new Node(z)).ToArray();
  199. }
  200.  
  201. public int Length => nodes.Length;
  202.  
  203. public Node this[int index] { get { return nodes[index]; } }
  204.  
  205.  
  206. public IEnumerable<Node> Nodes
  207. {
  208. get
  209. {
  210. foreach (var node in nodes) yield return node;
  211. }
  212. }
  213.  
  214. public Edge Connect(int index1, int index2)
  215. {
  216. return Node.Connect(nodes[index1], nodes[index2], this);
  217. }
  218.  
  219. public void Delete(Edge edge)
  220. {
  221. Node.Disconnect(edge);
  222. }
  223.  
  224. public IEnumerable<Edge> Edges
  225. {
  226. get
  227. {
  228. return nodes.SelectMany(z => z.IncidentEdges).Distinct();
  229. }
  230. }
  231.  
  232. public static Graph MakeGraph(params int[] incidentNodes)
  233. {
  234. var graph = new Graph(incidentNodes.Max() + 1);
  235. for (int i = 0; i < incidentNodes.Length - 1; i += 2)
  236. graph.Connect(incidentNodes[i], incidentNodes[i + 1]);
  237. return graph;
  238. }
  239. }
  240. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement