#include "cyberland.h" #include <vector> #include <queue> #include <cmath> struct Noeud { int index, poids; }; struct Chemin { double somme; int iNoeud, nbDivPris; bool operator< (const Chemin &autre) const { return somme > autre.somme; } }; const int MAX_NOEUDS = 1e5; std::vector<Noeud> voisins[MAX_NOEUDS]; int nbNoeuds, noeudArrivee, nbDivMax; int type[MAX_NOEUDS]; bool zeroAccessible[MAX_NOEUDS]; double dijkstra() { bool estPasse[nbNoeuds][nbDivMax];for (int i = 0; i < nbNoeuds; i++) for (int j = 0; j < nbNoeuds; j++) estPasse[i][j] = false; std::priority_queue<Chemin> aPasser; aPasser.push({0, noeudArrivee, 0}); while (aPasser.size() != 0) { Chemin cheminCourant = aPasser.top(); aPasser.pop(); { estPasse[cheminCourant.iNoeud][cheminCourant.nbDivPris] = true; if (zeroAccessible[cheminCourant.iNoeud]) { return cheminCourant.somme; } double somme = cheminCourant.somme; // on ajoute les voisins for (int iVoisin = 0; iVoisin < voisins[cheminCourant.iNoeud].size(); iVoisin++) { double nouvelleSomme; int voisin = voisins[cheminCourant.iNoeud][iVoisin].index; nouvelleSomme = somme + voisins[cheminCourant.iNoeud][iVoisin].poids / pow(2, cheminCourant.nbDivPris); // on le fait en prennant ou non la division si possible if (!estPasse[voisin][cheminCourant.nbDivPris]) { estPasse[voisin][cheminCourant.nbDivPris] = true; aPasser.push({nouvelleSomme, voisin, cheminCourant.nbDivPris}); } if (!estPasse[voisin][cheminCourant.nbDivPris+1] && type[voisin] == 2 && cheminCourant.nbDivPris < nbDivMax) { estPasse[voisin][cheminCourant.nbDivPris+1] = true; aPasser.push({nouvelleSomme, voisin, cheminCourant.nbDivPris+1}); } } } } return -1; } double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) { nbNoeuds = N; noeudArrivee = H; nbDivMax = K; for (int i = 0; i < M; i++) { voisins[x[i]].push_back({y[i], c[i]}); voisins[y[i]].push_back({x[i], c[i]}); } for (int i = 0; i < nbNoeuds; i++) { type[i] = arr[i]; } // on fait un bfs pour savoir quelles cases qui mettent 0 sont accessibles std::queue<int> aPasser; bool estPasse[nbNoeuds]; for (int i = 0; i < nbNoeuds; i++)estPasse[i] = false; aPasser.push(0); while (aPasser.size() != 0) { int iCourant = aPasser.front(); aPasser.pop(); if (!estPasse[iCourant] && iCourant != H) { if (type[iCourant] == 0) { zeroAccessible[iCourant] = true; } estPasse[iCourant] = true; for (int iVoisin = 0; iVoisin < voisins[iCourant].size(); iVoisin++) { aPasser.push(voisins[iCourant][iVoisin].index); } } } zeroAccessible[0] = true; return dijkstra(); }

cyberland.cpp: In function 'double dijkstra()':
cyberland.cpp:51:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Noeud>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |             for (int iVoisin = 0; iVoisin < voisins[cheminCourant.iNoeud].size(); iVoisin++)
      |                                   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:114:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Noeud>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |             for (int iVoisin = 0; iVoisin < voisins[iCourant].size(); iVoisin++)
      |                                   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~