Advertisement
Guest User

Nao sei onde ta o erro guys

a guest
Nov 15th, 2019
141
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.29 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define INF 0x3f3f3f3f
  3. #define x first
  4. #define y second
  5. using namespace std;
  6.  
  7. int main(){
  8. int qtd_fases;
  9. cin >> qtd_fases;
  10.  
  11. for(int u = 0; u < qtd_fases; u++){
  12. int qtd_pontos;
  13. cin >> qtd_pontos;
  14.  
  15. int distancia[qtd_pontos], precursores[qtd_pontos];
  16. pair<int, int> pontos[qtd_pontos]; //Guarda o ponto
  17. bool moedas[qtd_pontos]; //Guarda se tem moeda
  18. unordered_map <int, list<pair<int, int>>> adjacencias; //Guarda o adjacente + peso aresta
  19.  
  20. for(int j = 0 ; j < qtd_pontos; j++) {
  21. distancia[j] = INF;
  22. precursores[j] = -1;
  23. moedas[j] = false;
  24. }
  25.  
  26. for(int j = 0; j < qtd_pontos; j++){ //Coleta as coordenadas dos pontos
  27. int x, y;
  28. cin >> x >> y;
  29. pontos[j] = make_pair(x, y);
  30. }
  31.  
  32. int qtd_moedas;
  33. cin >> qtd_moedas;
  34. for(int j = 0; j < qtd_moedas; j++){
  35. int posicao;
  36. cin >> posicao;
  37. moedas[posicao] = true;
  38. }
  39.  
  40. for(int j = 0; j < qtd_pontos; j++){
  41. int qtd_alcancaveis;
  42. cin >> qtd_alcancaveis;
  43.  
  44. for(int i = 0; i < qtd_alcancaveis; i++){
  45. int aux;
  46. cin >> aux;
  47. int distancia = pow((pontos[j].x - pontos[aux].x),2) + pow((pontos[j].y - pontos[aux].y),2);
  48. if(moedas[aux] == true)
  49. adjacencias[j].push_back(make_pair(aux, -distancia));
  50.  
  51. else
  52. adjacencias[j].push_back(make_pair(aux, distancia));
  53. }
  54. }
  55. //INICIO DO BELLMAN-FORD
  56. distancia[0] = 0;
  57. for(int i = 1; i < qtd_pontos-1; i++){ //Varre os vertices
  58. for(auto r: adjacencias[i]){ //Varre a lista de adj. de cada vertice
  59. if(distancia[i] == INF || distancia[r.x] > distancia[i] + r.y){
  60. distancia[r.x] = distancia[i] + r.y;
  61. precursores[r.x] = i;
  62. }
  63. }
  64. }
  65. bool stop = false;
  66. for(int i = 1; i < qtd_pontos && !stop; i++){ //Checa se ha loops
  67. for(auto r: adjacencias[i]){
  68. if(distancia[r.x] > distancia[i] + r.y)
  69. stop = true;
  70. }
  71. }
  72. if(stop == false){
  73. int energia = 0;
  74.  
  75. bool aux = false;
  76. vector<int> print;
  77. int aux2 = qtd_pontos-1;
  78.  
  79. while(!aux) {
  80. print.push_back(precursores[aux2]);
  81. aux2 = precursores[aux2];
  82. if(precursores[aux2] == 0)
  83. aux = true;
  84. }
  85. for(int i = print.size()-1; i > 0; i++){
  86. for(auto s : adjacencias[print[i]]){
  87. if(s.x == i) energia += s.y;
  88. }
  89. }
  90. cout << energia << " ";
  91. for(int i = print.size()-1; i >= 0; i--) cout << print[i] << " ";
  92. cout << endl;
  93. }
  94. else cout << "LOOP" << endl;
  95.  
  96. string a;
  97. getline(cin, a);
  98. }
  99. return 0;
  100. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement