#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <fstream>
#define INF 100000
const int N=24;
using namespace std;

int minD(vector<int>* mas,int *key){
    vector<int>::iterator min=mas->begin();
    for(vector<int>::iterator i=min+1;i<mas->end();i++) if(key[*i]<=key[*min]) min=i;
    int edge=*min;
    mas->erase(min);
    return edge;
}

void Prima(int **in,int **out){
    vector<int> unvisited;
    int u,v;
    int dist[N];
    int path[N];
    //----------------------clear
    for(int i=0;i<N;i++)
    for(int j=0;j<N;j++) out[i][j]=0;
    //--------------------filling_on_first
    for(int i=0;i<N;i++){
        unvisited.push_back(i);
        dist[i]=INF;
        path[i]=0;
    }
    //----------------------------preparation
    dist[0]=0;
    u=minD(&unvisited,dist);
    //-------------------------algorithm
    while(unvisited.empty()==false){
        for(int i=0;i<N;i++){
            if(i==u || in[u][i]<1) continue;
            if(find(unvisited.begin(),unvisited.end(),i)!=unvisited.end() && in[u][i]<dist[i]){
                dist[i]=in[u][i];
                path[i]=u;
                }
        }
            u=minD(&unvisited,dist);
            //cout<<unvisited.size()<<endl;
    }
    for(int i=0;i<N;i++) {
        if(dist[i]==INF) dist[i]=0;
        out[path[i]][i]=dist[i];
        out[i][path[i]]=dist[i];
    }

}

void printGraph(int **mas){
    cout<<"   ";
    for(int i=0;i<N;i++) {
        if(i<10) cout<<' ';
        cout<<' '<<i;
    }
    cout<<endl<<"  ";
    for(int i=0;i<N;i++) cout<<"___";
    cout<<endl;
    for(int i=0;i<N;i++){
        if(i<10) cout<<' ';
        cout<<i<<"| "<<mas[i][0];
        for(int j=1;j<N;j++) {
            if(mas[i][j]>9) cout<<' '; else cout<<"  ";
            cout<<mas[i][j];
        }
        cout<<endl;
    }
}

void clearM(int **mas){
    for(int i=0;i<N;i++){
        delete [] mas[i];
    }
    delete [] mas;
}

int main() {
    ifstream in("test.txt");
    int** graph=new int*[N];
    for(int i=0;i<N;i++) graph[i]=new int[N];
    int** tree=new int*[N];
    for(int i=0;i<N;i++) tree[i]=new int[N];
    for(int i=0;i<N;i++)
    for(int j=0;j<N;j++) in>>graph[i][j];
    for(int i=0;i<N;i++)
    for(int j=0;j<N;j++) if(i<j) graph[j][i]=graph[i][j];
    in.close();
    printGraph(graph);
    Prima(graph,tree);
    cout<<"Tree:\n";
    printGraph(tree);
    clearM(graph);
    clearM(tree);
    return 0;
}