fork download
copy 
  1.     using System;
  2.     using System.Collections.Generic;
  3.     using System.Linq;
  4.     using System.Text;
  5.     using System.Threading.Tasks;
  6.  
  7.     namespace Grafos {
  8.         public static class Djiskstra {
  9.             /// <summary>
  10.             /// https://j...content-available-to-author-only...d.com/pt/problems/view/1148
  11.             /// </summary>
  12.             public static void Test() {
  13.                 reset:
  14.                 string line = Console.ReadLine();
  15.                 int QtdCidades = int.Parse(line.Split(' ')[0]);
  16.                 int QtdLinhas  = int.Parse(line.Split(' ')[1]);
  17.                 if (QtdCidades == 0 && QtdLinhas == 0) { return; }
  18.  
  19.                 Graph graph = new Graph(true);
  20.                 for (int i = 1; i <= QtdCidades; i++) {
  21.                     graph.AddNode(i.ToString());
  22.                 }
  23.  
  24.                 for (int i = 0; i < QtdLinhas; i++) {
  25.                     line = Console.ReadLine();
  26.                     string Cidade1 = line.Split(' ')[0];
  27.                     string Cidade2 = line.Split(' ')[1];
  28.                     int Value = int.Parse(line.Split(' ')[2]);
  29.  
  30.                     Node Cid1 = graph.lstNodes.First(p => p.Data == Cidade1);
  31.                     Node Cid2 = graph.lstNodes.First(p => p.Data == Cidade2);
  32.  
  33.                     List<Aresta> lstConnections = Cid2.lstConnections.Where(a => a.Destination == Cid1).ToList();
  34.                     if (lstConnections.Count > 0) {
  35.                         Value = 0;
  36.                         foreach (var item in lstConnections) {
  37.                             item.Value = 0;
  38.                         }
  39.                     }
  40.                     graph.AddAresta(Cid1, Cid2, Value);
  41.                 }
  42.  
  43.  
  44.                 line = Console.ReadLine();
  45.                 if(line.Split(' ').Length > 2) { return; }
  46.                 int QtdConsultas = int.Parse(line.Trim());
  47.  
  48.                 for (int i = 0; i < QtdConsultas; i++) {
  49.                     line = Console.ReadLine();
  50.                     string Cidade1 = line.Split(' ')[0];
  51.                     string Cidade2 = line.Split(' ')[1];
  52.                     Node mCidade1 = graph.lstNodes.First(p => p.Data == Cidade1);
  53.                     Node mCidade2 = graph.lstNodes.First(p => p.Data == Cidade2);
  54.                     int? Result = Run(graph, mCidade1, mCidade2);
  55.                     Console.WriteLine(Result != null ? Result.ToString() : "Nao e possivel entregar a carta");
  56.                 }
  57.                 goto reset;
  58.             }
  59.  
  60.             public static int? Run(Graph mGraph, Node Source, Node Target) {
  61.                 List<DjikstraObj> lstNodes = mGraph.lstNodes.Select(p => new DjikstraObj(p, null)).ToList();
  62.  
  63.                 DjikstraObj mNodeCorrente = lstNodes.First(p => p.Node == Source);
  64.                 mNodeCorrente.Distance = 0;
  65.  
  66.                 while (lstNodes.Any(p => !p.Visited)) {
  67.                     List<DjikstraObj> lstNeighbors =
  68.                         lstNodes.Where(p => !p.Visited).Where(n =>
  69.                             //Destinos do nó corrente
  70.                             mNodeCorrente.Node.lstConnections.Select(p => p.Destination)
  71.                         .Contains(n.Node)).ToList(); 
  72.  
  73.                     foreach (DjikstraObj mNeighbor in lstNeighbors) {
  74.                         int? TentativeDistance = mNodeCorrente.Distance + mNodeCorrente.Node.lstConnections.First(p => p.Destination == mNeighbor.Node).Value;
  75.  
  76.                         // Update the neighbor's distance if the tentative distance is smaller
  77.                         if (TentativeDistance != null && (mNeighbor.Distance == null || TentativeDistance < mNeighbor.Distance)) {
  78.                             mNeighbor.Distance = TentativeDistance.Value;
  79.                         }
  80.                     }
  81.  
  82.                     mNodeCorrente.Visited = true;
  83.  
  84.                     // If there are no more unvisited nodes with distances, break out of the loop
  85.                     if(lstNodes.Where(p => !p.Visited).All(p => p.Distance == null)) { 
  86.                         break; 
  87.                     }
  88.  
  89.                     // Get the unvisited node with the smallest distance
  90.                     mNodeCorrente = lstNodes.Where(p => !p.Visited && p.Distance != null)
  91.                                         .OrderBy(p => p.Distance)
  92.                                         .FirstOrDefault();
  93.  
  94.                     if(mNodeCorrente == null) { 
  95.                         break; 
  96.                     }
  97.                 }
  98.  
  99.                 // Return the distance to the target node
  100.                 return lstNodes.First(p => p.Node == Target).Distance;
  101.             }
  102.  
  103.             public class DjikstraObj {
  104.                 public Node Node { get; set; }
  105.                 public int? Distance { get; set; }
  106.                 public bool Visited { get; set; } = false;
  107.  
  108.                 public DjikstraObj(Node Node, int? Distance) {
  109.                     this.Node = Node;
  110.                     this.Distance = Distance;
  111.                 }
  112.             }
  113.         }
  114.     }
  115.  
  116.     namespace Grafos {
  117.         // Node class representing vertices in the graph
  118.         public class Node {
  119.             public string Data { get; set; }
  120.             public List<Aresta> lstConnections { get; set; } = new List<Aresta>();
  121.  
  122.             public Node(string Data = default(string)) {
  123.                 this.Data = Data;
  124.             }
  125.  
  126.             public override string ToString() {
  127.                 return Data != null ?  $"{Data}" : "null";
  128.             }
  129.         }
  130.  
  131.         // Edge class representing connections between nodes
  132.         public class Aresta {
  133.             public int Value { get; set; }
  134.             public Node Source { get; set; }
  135.             public Node Destination { get; set; }
  136.  
  137.             public Aresta(Node source, Node destination, int Value = 0) {
  138.                 Source = source;
  139.                 Destination = destination;
  140.                 this.Value = Value;
  141.             }
  142.  
  143.             public override string ToString() {
  144.                 return $"[{Value}, {Source} -> {Destination}]";
  145.             }
  146.         }
  147.  
  148.         // Graph class to manage nodes and connections
  149.         public class Graph {
  150.             public List<Node> lstNodes = new List<Node>();
  151.             private bool isDirected = false;
  152.  
  153.             public Graph(bool directed = false) {
  154.                 isDirected = directed;
  155.             }
  156.  
  157.             public List<Aresta> lstAresta {
  158.                 get {
  159.                     return SelectMany(lstNodes, p => p.lstConnections).ToList();
  160.                 }
  161.             }
  162.  
  163.         public static IEnumerable<TResult> SelectMany<TSource, TResult>(
  164.         IEnumerable<TSource> source,
  165.         Func<TSource, IEnumerable<TResult>> selector) {
  166.                 foreach (var item in source) {
  167.                     foreach (var subItem in selector(item)) {
  168.                         yield return subItem;
  169.                     }
  170.                 }
  171.             }
  172.  
  173.  
  174.             // Add a node to the graph
  175.             public Node AddNode(string data) {
  176.                 var node = new Node(data);
  177.                 lstNodes.Add(node);
  178.                 return node;
  179.             }
  180.  
  181.             // Add an edge between two nodes
  182.             public void AddAresta(Node source, Node destination, int Value = 0) {
  183.                 var edge = new Aresta(source, destination, Value);
  184.                 source.lstConnections.Add(edge);
  185.  
  186.                 if (!isDirected) {
  187.                     var reverseEdge = new Aresta(destination, source, Value);
  188.                     destination.lstConnections.Add(reverseEdge);
  189.                 }
  190.             }
  191.  
  192.             // Print the graph
  193.             public void PrintGraph() {
  194.                 foreach (var node in lstNodes) {
  195.                     Console.Write($"Node {node.Data}: ");
  196.                     foreach (var edge in node.lstConnections) {
  197.                         Console.Write($"({edge.Destination.Data}) ");
  198.                     }
  199.                     Console.WriteLine();
  200.                 }
  201.             }
  202.         }
  203.     }
  204.  
  205. namespace Grafos {
  206.     public static class Program {
  207.         static void Main(string[] args) {
  208.             Djiskstra.Test();
  209.         }
  210.     }
  211.  
  212. }
Success #stdin #stdout 0.07s 33564KB
comments (?)
stdin
copy 
4 5
1 2 5
2 1 10
3 4 8
4 3 7
2 3 6
5
1 2
1 3
1 4
4 3
4 1
3 3
1 2 10
2 3 1
3 2 1
3
1 3
3 1
3 2
0 0
stdout
copy 
0
6
6
0
Nao e possivel entregar a carta
10
Nao e possivel entregar a carta
0
https://ideone.com/lGj2pZ
language:
C# (NET 6.0)
created:
22 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!