fork download
copy 
  1. using System;
  2. using System.Collections;
  3. using System.Collections.Generic;
  4.  
  5. namespace Desvio
  6. {
  7.     class Program
  8.     {
  9.         static int n, m, c, k;
  10.         static int[,] grafo = new int[1010, 1010];
  11.         static int[] custo = new int[1010];
  12.         static int inf = 99999;
  13.         static Queue<int> fila = new Queue<int>();
  14.  
  15.         static int dijkstra(int origem, int destino)
  16.         {
  17.             custo[origem] = 0;
  18.             fila.Enqueue(origem);
  19.             while(fila.Count != 0)
  20.             {
  21.                 int i = fila.Dequeue();
  22.                 for(int j=0; j < n; j++)
  23.                 {
  24.                     if(grafo[i,j] != inf && custo[j] > custo[i] + grafo[i,j])
  25.                     {
  26.                         custo[j] = custo[i] + grafo[i, j];
  27.                         fila.Enqueue(j);
  28.                     }
  29.                 }
  30.             }
  31.  
  32.             return custo[destino];
  33.         }
  34.  
  35.  
  36.         static void Main(string[] args)
  37.         {
  38.             do
  39.             {
  40.                 string entrada = Console.ReadLine();
  41.                 n = int.Parse(entrada.Split(' ')[0]);
  42.                 m = int.Parse(entrada.Split(' ')[1]);
  43.                 c = int.Parse(entrada.Split(' ')[2]);
  44.                 k = int.Parse(entrada.Split(' ')[3]);
  45.  
  46.  
  47.                 if (n != 0 && m != 0 && c != 0 && k != 0)
  48.                 {
  49.  
  50.  
  51.  
  52.                     for (int i = 0; i <= n; i++)
  53.                     {
  54.                         custo[i] = inf;
  55.  
  56.                         for (int j = 0; j <= n; j++)
  57.                         {
  58.                             grafo[i, j] = inf;
  59.                         }
  60.                     }
  61.  
  62.                     for (int i = 1; i <= m; i++)
  63.                     {
  64.                         int u, v, p;
  65.                         string entradaAresta = Console.ReadLine();
  66.                         u = int.Parse(entradaAresta.Split(' ')[0]);
  67.                         v = int.Parse(entradaAresta.Split(' ')[1]);
  68.                         p = int.Parse(entradaAresta.Split(' ')[2]);
  69.  
  70.                         if (u >= c && v >= c)
  71.                         {
  72.                             grafo[u, v] = p;
  73.                             grafo[v, u] = p;
  74.                         }
  75.  
  76.                         if (u >= c && v < c)
  77.                         {
  78.                             grafo[u, v] = p;
  79.                         }
  80.  
  81.                         if (u < c && v >= c)
  82.                         {
  83.                             grafo[v, u] = p;
  84.                         }
  85.  
  86.                         if (u < c && v < c && Math.Abs(u - v) == 1)
  87.                         {
  88.                             grafo[u, v] = p;
  89.                             grafo[v, u] = p;
  90.                         }
  91.  
  92.  
  93.  
  94.                     }
  95.  
  96.  
  97.                     int resultado = dijkstra(k, c - 1);
  98.                     Console.WriteLine(resultado);
  99.                 }
  100.             } while (n != 0 && m != 0 && c != 0 && k != 0);
  101.  
  102.             //Console.ReadKey();
  103.         }
  104.     }
  105.  
  106.  
  107. }
Success #stdin #stdout 0.02s 17428KB
comments (?)
stdin
copy 
4 6 3 3
0 1 10
1 2 10
0 2 1
3 0 1
3 1 10
3 2 10
6 7 2 5
5 2 1
2 1 10
1 0 1
3 0 2
3 4 2
3 5 3
5 4 2
5 5 2 4
0 1 1
1 2 2
2 3 3
3 4 4
4 0 5
0 0 0 0
stdout
copy 
10
6
6
https://ideone.com/1m98Uj
language:
C# (gmcs 5.20.1)
created:
4 years 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!