API tools faq
paste
Guest User

Untitled

a guest
Sep 9th, 2018
195
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.96 KB | None | 0 0
raw download clone embed print report
  1. import java.util.Scanner;
  2. import java.util.ArrayList;
  3. import java.util.HashMap;
  4. import java.util.LinkedList;
  5.  
  6. class Cidade{
  7.  
  8. HashMap<Integer, Integer> rodovias = new HashMap<Integer, Integer>();
  9.  
  10. public void addRodovia(int destino, int comprimento) {
  11.  
  12. this.rodovias.put(destino, comprimento);
  13.  
  14. }
  15.  
  16. }
  17.  
  18. public class Main {
  19.  
  20. public static void main(String[] args) {
  21.  
  22. Scanner sc = new Scanner(System.in);
  23. HashMap<Integer, Cidade> listaCidades = new HashMap<Integer, Cidade>();
  24. int numCidades, numRodovias;
  25. int indiceOrigem, indiceDestino, comprimentoRodovia;
  26.  
  27. while(sc.hasNext()) {
  28.  
  29. numCidades = sc.nextInt();
  30. numRodovias = sc.nextInt();
  31.  
  32. for(int i = 0; i < numCidades; i++) {
  33.  
  34. Cidade cidade = new Cidade();
  35. listaCidades.put(i+1, cidade);
  36.  
  37. }
  38.  
  39. for(int i = 0; i < numRodovias; i++) {
  40.  
  41. indiceOrigem = sc.nextInt();
  42. indiceDestino = sc.nextInt();
  43. comprimentoRodovia = sc.nextInt();
  44. listaCidades.get(indiceOrigem).addRodovia(indiceDestino, comprimentoRodovia);
  45. listaCidades.get(indiceDestino).addRodovia(indiceOrigem, comprimentoRodovia);
  46.  
  47. }
  48.  
  49. System.out.printf("%d", somaComprimentos(listaCidades));
  50.  
  51. }
  52.  
  53. sc.close();
  54.  
  55. }
  56.  
  57. public static int somaComprimentos(HashMap<Integer, Cidade> listaCidades) {
  58.  
  59. HashMap<Integer, Integer> distancia = new HashMap<Integer, Integer>();
  60. ArrayList<Integer> visitado = new ArrayList<Integer>();
  61. int resp = 0;
  62. int atual = 1;
  63.  
  64. distancia.put(atual, 0);
  65. visitado.add(atual);
  66.  
  67. for(int i = 0; i < listaCidades.size() - 1; i++) {
  68.  
  69. distancia = atualizaDistancias(listaCidades, distancia, visitado, atual);
  70. distancia.remove(atual);
  71. atual = buscaMenorDistancia(distancia);
  72. resp = resp + distancia.get(atual);
  73. distancia.put(atual, 0);
  74. visitado.add(atual);
  75.  
  76. }
  77.  
  78. return resp;
  79.  
  80. }
  81.  
  82. public static HashMap<Integer, Integer> atualizaDistancias (HashMap<Integer, Cidade> listaCidades, HashMap<Integer, Integer> distancia, ArrayList<Integer> visitado, int atual) {
  83.  
  84. for(Integer cidadeVizinha : listaCidades.get(atual).rodovias.keySet()) {
  85.  
  86. int valor = listaCidades.get(atual).rodovias.get(cidadeVizinha);
  87.  
  88. if(visitado.contains(cidadeVizinha)) continue;
  89.  
  90. if(!distancia.containsKey(cidadeVizinha)) {
  91.  
  92. distancia.put(cidadeVizinha, valor);
  93. continue;
  94.  
  95. }
  96. else {
  97.  
  98. if(distancia.get(cidadeVizinha) > valor){
  99.  
  100. distancia.put(cidadeVizinha, valor);
  101.  
  102. }
  103.  
  104. }
  105.  
  106. }
  107.  
  108. return distancia;
  109.  
  110. }
  111.  
  112. public static int buscaMenorDistancia (HashMap<Integer, Integer> distancia) {
  113.  
  114. int distanciaMenor = Integer.MAX_VALUE;
  115. int indiceMenor = -1;
  116.  
  117. for(int indice : distancia.keySet()) {
  118.  
  119. if(distancia.get(indice) < distanciaMenor) {
  120.  
  121. distanciaMenor = distancia.get(indice);
  122. indiceMenor = indice;
  123.  
  124. }
  125.  
  126. }
  127.  
  128. return indiceMenor;
  129.  
  130. }
  131.  
  132. }
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!