PRIR

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

struct DrogaKomiwojazera
{
	float kosztDrogi;
	int * przebytaDroga;
};

void wczytaj_macierz(std::ifstream & plik, float ** macierz, int & rozmiar);
void zwolnij_pamiec(float ** macierz, int rozmiar);
float koszt_drogi(float ** macierz, const int * p, int rozmiar);

int _tmain(int argc, _TCHAR* argv[])
{
	std::ifstream plik;
	int rozmiar;
	using namespace std;
	plik.open("we.txt");
	plik >> rozmiar;
	plik.get();
	float ** macierz = new float*[rozmiar];
	for (int i = 0; i < rozmiar; i++) {
		macierz[i] = new float[rozmiar];
	}
	wczytaj_macierz(plik, macierz, rozmiar);
	plik.close();
	int* miasta = new int[rozmiar];
	for (int i = 0; i < rozmiar; i++)
	{
		miasta[i] = i;
	}
	DrogaKomiwojazera najlepszaDroga;
	najlepszaDroga.przebytaDroga = new int[rozmiar];
	najlepszaDroga.kosztDrogi = koszt_drogi(macierz, miasta, rozmiar);
	bool loop = true;
	while (loop)
	{
		loop = next_permutation(miasta, miasta + rozmiar);
		float droga = koszt_drogi(macierz, miasta, rozmiar);
		if (droga < najlepszaDroga.kosztDrogi)
		{
			najlepszaDroga.kosztDrogi = droga;
			for (int i = 0; i < rozmiar; i++) {
				najlepszaDroga.przebytaDroga[i] = miasta[i];
			}
			cout << "Najlepsza droga: ";
			for (int i = 0; i< rozmiar; i++)
				cout << miasta[i] << ", ";
			cout << endl;
			cout << "Koszt najkrótszej drogi: " << najlepszaDroga.kosztDrogi << endl;
		}
	}
	cout << "Najlepsza droga: ";
	for (int i = 0; i< rozmiar; i++)
		cout << najlepszaDroga.przebytaDroga[i] << ", ";
	cout << endl;
	cout << "Koszt najkrótszej drogi: " << najlepszaDroga.kosztDrogi << endl;
	cin.get();
	zwolnij_pamiec(macierz, rozmiar);
	return 0;
}

void wczytaj_macierz(std::ifstream & plik, float ** macierz, int & rozmiar)
{
	for (int i = 0; i < rozmiar; i++)
	{
		for (int j = 0; j < rozmiar; j++)
			plik >> macierz[i][j];
	}
}

void zwolnij_pamiec(float ** macierz, int rozmiar)
{
	for (int i = 0; i < rozmiar; i++) {
		delete macierz[i];
	}
	delete[] macierz;
}

float koszt_drogi(float ** macierz, const int * p, int rozmiar)
{
	DrogaKomiwojazera droga;
	float kosztDrogi = 0.0f;
	for (int i = 0; i < rozmiar; i++)
	{
		int x = i;
		int y = i + 1;
		if (i + 1 == rozmiar) {
			y = 0;
		}
		kosztDrogi += macierz[p[i]][p[y]];
	}
	return kosztDrogi;
}