Untitled

 avatar
unknown
plain_text
2 years ago
2.0 kB
6
Indexable
#include<bits/stdc++.h>
using namespace std;
const int N=5;
double minCostMST(vector<vector<int>>&graph,vector<bool>&visited)
{
    vector<int>key(N,numeric_limits<int>::min());
    key[0]=0.0;
    double minCost=0;
    for(int cnt=0;cnt<N-1;++cnt)

    {
        int u=-1;
        for(int v=0;v<N;++v)
        {
            if(!visited[v]&&(u==-1||key[v]<key[u])){
                u=v;
            }
        }
        visited[u]=true;
        minCost+=key[u];
        for(int v=0;v<N;v++)
        {
            if(!visited[v]&&graph[u][v]<key[v]){
                key[v]=graph[u][v];
            }
        }
    }
    return minCost;

}

vector<int> tspMST(vector<vector<int>>&graph){
    vector<bool>visited(N,false);
    double minCost=minCostMST(graph,visited);
    vector<int>tour={0};
    int currentCity=0;

    for(int i=1;i<N;i++)
    {
        int nextCity=-1;
        double minEdge=numeric_limits<int>::min();
        for(int j=0;j<N;j++)
        {
            if(!visited[j]&&graph[currentCity][j]<minEdge){
            minEdge=graph[currentCity][j];
            nextCity=j;
        }
    }
    if(nextCity!=-1){
        tour.push_back(nextCity);
        visited[nextCity]=true;
        currentCity=nextCity;

    }
}
  tour.push_back(0);
  return tour;
}

int main()
{
   // vector<pair<int,int>>cities(5);
    vector<vector<int>>graph(N,vector<int>(N,0));
    for(int i=0;i<5;i++)
    {
        for(int j=0;j<N;j++)
        {
            int u,v,w;
            cin>>u>>v>>w;
           graph[u][v]=w;
           graph[v][u]=w;
        }
    }

    vector<int>tour(N);
    tour=tspMSt(graph);
                                                                                                                                                                                                                            tour=tspMST(graph);
    for(int city:tour)
    {
        cout<<city<<" ";
    }
    cout<<endl;
}
Editor is loading...