fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. using namespace std;
  5.  
  6. void zeraGrafo(int grafo[101][101])
  7. {
  8.     for(int i=0;i<101;i++)
  9.     {
  10.         for(int j=0;j<101;j++)
  11.         {
  12.             grafo[i][j] = 0;
  13.         }
  14.     }
  15. }
  16.  
  17. void zeraVisitados(int *visitados)
  18. {
  19.     for(int i=0;i<1001;i++)
  20.     {
  21.         visitados[i] = 0;
  22.     }
  23. }
  24.  
  25. void inicializaVetCustos(int *custos)
  26. {
  27.     for(int i=0;i<1001;i++)
  28.     {
  29.         custos[i] = 9999999;
  30.     }
  31. }
  32.  
  33. /*visits a vertex, updating the cost to visit any of its neighbours afterwards,
  34. then recursively visits the next cheapest vertex*/
  35. void visita(int grafo[101][101], int *visitados, int *custos, int localPartida, int destino, int *custoCaminho, int numLocais)
  36. {
  37.     int menorCusto = 9999999, proximoLocal = -1;
  38.  
  39.     visitados[localPartida] = 1;
  40.  
  41.     /*if the vertex we're visiting is the destination, we found our solution, so
  42.     update our final cost and return*/
  43.     if(localPartida==destino)
  44.     {
  45.         *(custoCaminho) = custos[destino];
  46.         return;
  47.     }
  48.  
  49.     /*update cost for each vertex, and search for the next cheapest vertex to
  50.     visit*/
  51.     for(int i=0;i<numLocais;i++)
  52.     {
  53.         if(grafo[localPartida][i] && ((custos[localPartida]+grafo[localPartida][i])<custos[i]))
  54.         {
  55.             custos[i] = (custos[localPartida] + grafo[localPartida][i]);
  56.         }
  57.  
  58.         if((custos[i]<menorCusto) && visitados[i]==0)
  59.         {
  60.             menorCusto = custos[i];
  61.             proximoLocal = i;
  62.         }
  63.     }
  64.  
  65.     /*if we found a vertex to visit, then visit it, otherwise there is no path
  66.     to our destination, and we return*/
  67.     if(proximoLocal>=0)
  68.     {
  69.         visita(grafo, visitados, custos, proximoLocal, destino, custoCaminho, numLocais);
  70.     }
  71.  
  72.     return;
  73. }
  74.  
  75. //funcao que inicializa a simulacao do algoritmo de dijkstra
  76. //percorrendo o caminho entre a cidade de partida e o destino
  77. //se um caminho entre as cidades for encontrado, retorna seu
  78. //custo, se não retorna -1
  79. int dijkstra(int grafo[101][101], int *visitados, int *custos, int partida, int destino, int numLocais)
  80. {
  81.     int custoCaminho = -1;
  82.  
  83.     zeraVisitados(visitados);
  84.     inicializaVetCustos(custos);
  85.  
  86.     //seta o custo da cidade de partida com zero e faz a visita
  87.     //de todos os outros vértices, calculando e atualizando os
  88.     //custos
  89.     custos[partida] = 0;
  90.     visita(grafo, visitados, custos, partida, destino, &custoCaminho, numLocais);
  91.  
  92.     return custoCaminho;
  93. }
  94.  
  95. int main(int argc, char *argv[])
  96. {
  97.     int numLocais, numRuas, localI, localJ, partida, destino, custo;
  98.     int grafo[101][101];
  99.     int visitados[1001];
  100.     int custos[1001];
  101.  
  102.     while(1)
  103.     {
  104.         zeraGrafo(grafo);
  105.  
  106.         scanf("%d %d", &numLocais, &numRuas);
  107.  
  108.         if(numLocais==0 && numRuas==0)
  109.         {
  110.             break;
  111.         }
  112.  
  113.         for(int i=0;i<numRuas;i++)
  114.         {
  115.             scanf("%d %d", &localI, &localJ);
  116.             scanf("%d", &grafo[localI-1][localJ-1]);
  117.         }
  118.  
  119.         scanf("%d %d", &partida, &destino);
  120.  
  121.         //calcula o custo do caminho, retornando-o
  122.         custo = dijkstra(grafo, visitados, custos, (partida-1), (destino-1), numLocais);
  123.  
  124.         printf("%d\n", custo);
  125.     }
  126.  
  127.     return 0;
  128. }
  129.  
Success #stdin #stdout 0s 15224KB
comments (?)
stdin
copy 
3 3
1 2 2
1 3 7
2 3 3
1 3
3 3
1 2 3
1 3 7
2 3 5
1 3
3 2
1 2 2
2 1 3
1 3
4 6
1 2 5
1 3 3
2 4 3
3 2 2
4 1 4
4 3 9
2 3
0 0
stdout
copy 
5
7
-1
10
https://ideone.com/mQRNCT
language:
C++ (gcc 8.3)
created:
7 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!