Untitled
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...