IMPLÉMENTATION DE MINIMUM SPANNING TREE POUR UNE SOCIÉTÉ D'AUTOROUTES

#include<iostream>
#include<queue>
   using namespace std;
           
   struct edge{
           
   
   
      char a,b;
      int d;       
   
   
              
      edge(char a,char b,int d){
              
      
      
         this->a=a;
         this->b=b;
         this->d=d;        
      }
   };


           
   struct compare{
           
              
      bool operator()(edge e1,edge e2){
              
      
         return e1.d>e2.d;   
      }
   };  


           
   int main(){
           
   
      freopen("grand.out","w",stdout);
      freopen("grand.in","r",stdin);      
      int n,distance,n_voisins;     
      char v,v_voisine;
      cin>>n;
      while(n!=0){
         priority_queue<edge,vector<edge>,compare> pQ;
         for(int i=0;i<n-1;i++){           
            cin>>v>>n_voisins;
         
            for(int j=0;j<n_voisins;j++){                        
               cin>>v_voisine>>distance;
               edge e(v,v_voisine,distance);
               pQ.push(e);
            }    
         }       
      
         bool ville[26][26];
         for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
               ville[i][j]=(i==j); 
         int min_distance=0;
      
         while(!pQ.empty()){         
            int v1=pQ.top().a-'A';
            int v2=pQ.top().b-'A';
            int d=pQ.top().d;
            pQ.pop();
            if(!ville[v1][v2])
            { min_distance+=d;              
               for(int i=0;i<n;i++)              
                  for(int j=0;j<n;j++)                  
                     if(ville[i][v1] && ville[v2][j])
                        ville[i][j]=ville[j][i]=true;     
            }                  
         
         
         }
         cout<<min_distance<<endl;
         cin>>n;
         
      }
      return 0;
   
   }