#include "stdafx.h"
#include<iostream>

 using namespace std;

 const int e=10;

int a,b,u,v,n,i,j,ne=1;
int visited[10]={0},mi,mincost=0,cost[e][e];

int smej(int n,int cost[e][e])
{
	 cout<<"Введiть матрицю сумiжностi\n";

    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    {
        cin>>cost[i][j];
        if(cost[i][j]==0)
            cost[i][j]=999;
    }
	return cost[e][e];
}

int minpath(int n,int path[])
{

    int path_index=0;
	 while(ne < n)
    {
		mi =999;
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				if(cost[i][j]< mi)
					if(visited[i]!=0)
					{
						mi=cost[i][j];
						a=u=i;
						b=v=j;
					}
		if(visited[u]==0 || visited[v]==0)
        {
            path[path_index]=b;
            path_index++;
            ne++;
            mincost+=mi;
            visited[b]=1;
        }
        cost[a][b]=cost[b][a]=999;
    }
	 return *path;
}

void out(int n,int path[])
{
	cout<<1<<" --> ";
    for (int i=0;i<n-1;i++)
    {
		cout<<path[i];
		if (i<n-2) cout<<" --> ";
    }

    cout<<"\n Найменша довжина: "<<mincost<<endl;

}



int _tmain(int argc, _TCHAR* argv[])
{
	setlocale(LC_ALL,"rus");
	int path[100]={0};

    cout<<"Введiть кiлькiсть вершин"; cin>>n;
	**cost=smej(n,cost);
    visited[1]=1;
    cout<<"\n";
	*path=minpath(n,path);
    cout<<"\n";
	out(n,path);
	return 0;
}