GraphProblem.txt

int Solution::solve(int A, vector<vector<int> > &B) {
    int m=B.size(),mw=INT_MAX,idx;
    vector<pair<int,int>> *l=new vector<pair<int,int>> [A+1];
    for(int i=0;i<m;i++)
    {
        l[B[i][0]].push_back(make_pair(B[i][1],B[i][2]));
        l[B[i][1]].push_back(make_pair(B[i][0],B[i][2]));
        if(B[i][2]<mw)
         {
             mw=B[i][2];
             idx=B[i][0];
        }
    }
    int weights[A+1];
    int parents[A+1];
    for(int i=1;i<=A;i++)
    {
        parents[i]=-1;
        weights[i]=INT_MAX;
    }
    int visited[A+1]={0};
    weights[mw]=0;
    set<pair<int,int>> st;
    st.insert(make_pair(0,idx));
    while(!st.empty())
    {          
            pair<int,int> p=*st.begin();
            st.erase(st.begin());
        
            for(auto nbr:l[p.second])
            {
            
                int v=nbr.first;
                int w=nbr.second;
        
                if( visited[v]==0 && w<weights[v])
                {
                    parents[v]=p.second;
                    //weights[v]=w;
                    auto it=st.find(make_pair(weights[v],v));
                    if(it!=st.end())
                     st.erase(it);
                    weights[v]=w;
                    st.insert(make_pair(w,v));
                }
                
            }
           visited[p.second]=1;    
        
    }
    
    int ans=0;
    for(int i=1;i<=A;i++)
     {
         if(parents[i]!=-1)
          {
              ans+=weights[i];
              cout<<weights[i]<<" \n";
              cout<<i<<":"<<parents[i]<<"\n";
          }      
     }     
    return ans; 
}