#include <iostream>
#include <stdlib.h>
#include <windows.h>
#include <stdio.h>

#define N 6

using namespace std;

class list
{
public:
    int num;
    int ves;
    list *next;

	list(int n1, int n2)
	{
		num = n1;
		ves = n2;
		next=NULL;
	}
};

class matr
{
    public:
    list *ykaz[N];
	int oc_ver[N];
	bool bil[N];

	matr()
	{
		for (int i=0; i<N; i++)
		{
			ykaz[i]=NULL;
			bil[i]=NULL;
			oc_ver[i]=666;
		}

	}

	~matr()
	{
		list *del;
		for (int i=0; i<N; i++)
			{
				while (ykaz[i])
				{
					del=ykaz[i];
					ykaz[i]=ykaz[i]->next;
					delete del;
				}
			}
	}

	void poisk(int nnn)
	{
		int i;
		cout<<"переферия: "<<endl;
		int iii=0;
		for(i=0; i<N; i++)
			{
				if(oc_ver[i]>nnn)
					{
						cout<<" "<<i+1;
						iii++;
					}
			}
		if(iii==0)
		{
			cout<<" нет подходящих городов";
		}
	}

	void Dijkstra(int i_ver)
	{
		int i;
		list *temp;
		int min_ves_ver;
		oc_ver[--i_ver]=0;
		int begin=i_ver;
		while(i_ver<666)
			{
				temp=ykaz[i_ver];
				while (temp)
				{
					if(temp->ves<666 && (i_ver!=temp->num))
							{
								oc_ver[temp->num]=min(temp->ves+oc_ver[i_ver],oc_ver[temp->num]);
							}
					temp=temp->next;
				}

				bil[i_ver]=true;

				//поиск новой вершины
				min_ves_ver=i_ver=666;

				for(i=0; i<N; i++)
					{
						if(!(bil[i]))
							if(min_ves_ver>oc_ver[i])
								{
									min_ves_ver=oc_ver[i];
									i_ver=i;
								}
					}

			}
	}

    bool scet_is_faila() // считываем в матрицу
    {
		list *temp;
        FILE *f;
        char name[20];
        int n;
        cout<<"\n введите имя файла: ";
        scanf("%s",name);

        if((f=fopen(name,"rb"))== NULL)
            {
                cout<<"\n ошибка открытия файла \n";
                system("PAUSE");
                return 1;
            }

        // чтение матрицы весов из файла
        cout<<"матрица весов данного графа:"<<endl;

        for(int i=0; i<N; i++)
            {
                for(int j=0; j<N; j++)
                    {
                        fread(&n,sizeof(int),1, f);
                        printf("%4d ",n);
                        if(n<666)
                            if(ykaz[i]==NULL)
                                {
                                    ykaz[i]=new list(j,n);

                                }
                            else
                                {
                                    temp=ykaz[i];
                                    while(temp->next)
                                        {
                                            temp=temp->next;
                                        }
                                    temp->next=new list(j,n);
                                }
                    }
                cout<<endl;
            }
		return 0;
    }

};
int main()
{
    list *temp;
    matr mat;

    setlocale(LC_ALL, "Russian");

	// чтение матрицы весов из файла
    mat.scet_is_faila();

    for(int i=0;i<N; i++)
        {
            cout << "Для " << i+1 << " вершины ->";
            temp=mat.ykaz[i];
            while(temp)
            {
				cout << "(#"<< temp->num+1 << " вес=" << temp->ves << ") -> ";
                temp=temp->next;
            }
            cout<<"end"<<endl;
        }


    int i_ver; // пункт, с которого мы начинаем и заканчиваем
    cout<<"введите номер города, с которого следует расчитывать маршрут:";
    cin>>i_ver;
    mat.Dijkstra(i_ver);

	for (int i=0; i<N; i++)
	{
		cout << mat.oc_ver[i] << " ";
	}
	cout << endl;
    int nnn;
    cout<<"введите N, для расчета переферии: "<<endl;
    cin>>nnn;
	mat.poisk(nnn);
	cout << endl;

    return 0;
}