// Graph.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <time.h>
#include <stdlib.h>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <fstream>

#define INT_MAX       2147483640

using namespace std;
fstream in_file;
fstream out_file;


class GraphMatrice
{
public:
	//v - numarul de noduri din graf
	GraphMatrice(int V)
	{
		this->V = V;
		for (int i = 0; i < V; i++)
		{
			vector<int> vector;
			for (int j = 0; j < V; j++)
			{
				vector.push_back(-1); // o muchie nu exista daca este egala cu 0, deoarece pot exista muchii cu costul 0
			}
			graph.push_back(vector);
		}
	}

	void addMuchieCuCost(int deLa, int panaLa, int cost)
	{
		graph[deLa][panaLa] = cost;
	}

	//Functia principala, primeste ca argument nodul de la care pornim algoritmu
	void dijkstra(int sursa)
	{
		// Vectorul in care se vor salva distantele minime de la nodul sursa
		vector<int> distanta;
		vector<bool> vizitat; // Vectorul care ne va arata daca un nod a fost vizitat sau nu

		// Initializez distantele cu valoarea int maxima si vectorul de boolene ca nevizitate
		for (int i = 0; i < V; i++)
		{
			distanta.push_back(INT_MAX);
			vizitat.push_back(false);
		}

		// Distanta de la sursa este 0
		distanta[sursa] = 0;

		// Partea principala a algoritmului
		for (int i = 0; i < V - 1; i++)
		{
			// Alegem nodul cu distanta minima de la sura, nevizitat pentru a-l prelucra
			int u = distanta_minima(distanta, vizitat);

			// Dupa ce vizitam un nod il vom marca
			vizitat[u] = true;

			// Modificam distanta in matricea de adiacenta
			for (int v = 0; v < V; v++)
				//Modificam distanta pana la v doar daca nu este vizitata ,avem o muchie si daca distanta totala a caii de la sura la v prin u este mai mica decat cea curenta
			{
				if (!vizitat[v] && graph[u][v] >= 0 && distanta[u] + graph[u][v] < distanta[v])
					distanta[v] = distanta[u] + graph[u][v];
			}
		}

		// Printam distantele
		afisare_distante(distanta);
	}
private:
	int V;
	vector<vector<int>> graph;

	//Returneaza nodul nevizitat care se afla la distanta minima fata de sursa
	int distanta_minima(vector<int> distanta, vector<bool> vizitat)
	{
		int min = INT_MAX;	// initializam distanta minima cu valoarea maxima
		int min_index;	// indexul valorii minime

		for (int v = 0; v < V; v++)
			if (vizitat[v] == false && distanta[v] < min)
			{
				min = distanta[v];
				min_index = v;
			}
		return min_index;
	}

	// Functie ce afiseaza distantele (fara a mai afisa nodul sursa)
	void afisare_distante(vector<int> distanta)
	{
		//cout << "Nod\tDistanta de la nodul sursa\n";
		for (int i = 1; i < V; i++)
		{
			if (distanta[i] == INT_MAX)
			{
				out_file << 0 << " ";
			}
			else {
			out_file<< distanta[i] << " " ;
			}
		}
	}
};

// o structura pentru muchiile din bellman ford
struct BFMuchie {
	int sursa;
	int destinatie;
	int cost;
};

class GraphBellmanFord
{
public:
	// Constructor, primim numarul de varfuri si de muchii ale grafului
	GraphBellmanFord(int Varfuri, int Muchii) 
	{
		this->V = Varfuri;
		this->M = Muchii;
	}
	~GraphBellmanFord() {}

	void adaugaMuchieCuCost(int sursa, int destinatie, int cost)
	{
		BFMuchie muchie;
		muchie.sursa = sursa;
		muchie.destinatie = destinatie;
		muchie.cost = cost;
		muchii.push_back(muchie);
	}

	// Functia ce gaseste distantele minime de la nodul sursa la celelalte, functia detecteaza si ciclul negativ
	void BellmanFord(int src)
	{
		vector<int> distanta;

		// Initializam distanta de la sursa la restul ca infinit, apoi distanta pana la sursa ca 0
		for (int i = 0; i < V; i++)
			distanta.push_back(INT_MAX);
		distanta[src] = 0;

		// Relaxam muchiile de v-1 ori  deoarece putem avea cel mult v-1 muchii intre sursa si o destinatie
		for (int i = 1; i <= V - 1; i++) {
			for (int j = 0; j < M; j++) {
				int u = muchii[j].sursa;
				int v = muchii[j].destinatie;
				int cost = muchii[j].cost;
				if (distanta[u] != INT_MAX && distanta[u] + cost < distanta[v])
					distanta[v] = distanta[u] + cost;
			}
		}

		// Cautam cicluri negative. Pasul de mai sus garanteaza distantele daca nu avem cicluri negative. 
		// Daca acum obtinem un cost mai mic => avem cicluri negative
		for (int i = 0; i < M; i++) {
			int u = muchii[i].sursa;
			int v = muchii[i].destinatie;
			int cost = muchii[i].cost;
			if (distanta[u] != INT_MAX && distanta[u] + cost < distanta[v]) 
			{
				out_file << "Ciclu negativ!";
				return; // Daca am gasit un ciclu negativ, ne oprim dupa ce afisam mesajul
			}
		}

		for (int i = 1; i < V; i++)
			out_file << distanta[i] << " ";
		return;
	}

private:
	int V;	// Nr de varfuri
	int M;	// Nr de Muchii
	vector<BFMuchie> muchii;
};

//bool havelHakimi(vector<int>& grade, int n)
//{
//	//Repetam algoritmul pana cand una din conditii e indeplinita
//	while (true)
//	{
//		// Sortam descrescator
//		sort(grade.begin(), grade.end(), greater<>());
//
//		// Verificam daca toate elementele sunt egale cu 0
//		if (grade[0] == 0)
//			return true;
//
//		// Punem primul element in v si il eliminam din lista
//		int v = grade[0];
//		grade.erase(grade.begin() + 0);
//
//		// Verificam daca sunt destule elemente in lista
//		// Daca v este mai mic decat numarul de elemente din lista nu se poate construi un graf
//		if (v > grade.size())
//			return false;
//
//		// Scadem -1 din urmatoarele v elemente
//		for (int i = 0; i < v; i++)
//		{
//			grade[i]--;
//
//			// Verificam daca exista vreun element negativ dupa scadere
//			if (grade[i] < 0)
//				return false;
//		}
//	}
//}


int main()
{
	//belman-ford
	in_file.open("bellmanford.in");
	out_file.open("bellmanford.out", ios::out);

	int nr_varfuri;
	int nr_muchii;

	in_file >> nr_varfuri >> nr_muchii;

	GraphBellmanFord graph = GraphBellmanFord(nr_varfuri, nr_muchii);

	int varf1, varf2, cost;
	for (int i = 0; i < nr_muchii; i++)
	{
		in_file >> varf1 >> varf2 >> cost;
		graph.adaugaMuchieCuCost(varf1 - 1, varf2 - 1, cost);	//scad 1 deoarece am considerat nodurile de la 0
	}

	graph.BellmanFord(0);	// Pornim BF din primul nod

	//dijkstra
	/*
	in_file.open("dijkstra.in");
	out_file.open("dijkstra.out", ios::out);

	int nr_varfuri;
	int nr_arce;

	in_file >> nr_varfuri >> nr_arce;

	GraphMatrice graph = GraphMatrice(nr_varfuri);

	int varf1, varf2, cost;
	for (int i = 0; i < nr_arce; i++)
	{
		in_file >> varf1 >> varf2 >> cost;
		graph.addMuchieCuCost(varf1 - 1, varf2 - 1, cost);	//scad 1 deoarece am considerat nodurile de la 0
	}
	// Apelam dijkstra pentru a gasi distantele catre toate celelalte noduri
	graph.dijkstra(0);
	}
	*/

	//havel
	/*vector<int> a = {2,4,1,4,3};
	int n = a.size();
	if (havelHakimi(a, n))
		cout << "Da\n";
	else
		cout << "Nu\n";*/

	//sortaret
	/*
		in_file.open("sortaret.in");
		out_file.open("sortaret.out", ios::out);

		int nr_varfuri;
		int nr_arce;

		in_file >> nr_varfuri >> nr_arce;

		Graph graph = Graph(nr_varfuri);

		int varf1, varf2;
		for (int i = 0; i < nr_arce; i++)
		{
			in_file >> varf1 >> varf2;
			graph.addEdge(varf1 - 1, varf2 - 1);	//scad 1 deoarece am considerat nodurile de la 0
		}
		graph.sortareTopologica();
		*/

	//bfs
	/*
		in_file.open("bfs.in");
		out_file.open("bfs.out", ios::out);

		int nr_noduri, nr_arce, nod_plecare;
		in_file >> nr_noduri >> nr_arce >> nod_plecare;
		Graph graph = Graph(nr_noduri);
		int varf1, varf2;
		for (int i = 0; i < nr_arce; i++)
		{
			in_file >> varf1 >> varf2;
			graph.addEdge(varf1 - 1, varf2 - 1);	//scad 1 deoarece am considerat nodurile de la 0
		}
		graph.distantaCatreToateNodurile(nod_plecare);
		*/

	//dfs
	/*in_file.open("dfs.in");
		out_file.open("dfs.out", ios::out);

		int nr_varfuri, nr_arce;
		in_file >> nr_varfuri >> nr_arce;

		Graph graph = Graph(nr_varfuri);

		int varf1, varf2;
		for (int i = 0; i < nr_arce; i++)
		{
			in_file >> varf1 >> varf2;
			graph.addEdge(varf1 - 1, varf2 - 1);	//scad 1 deoarece am considerat nodurile de la 0
		}

		// Creez vectorul de noduri vizitate
		vector<bool> noduri_vizitate;
		for (int i = 0; i < nr_varfuri; i++)
		{
			noduri_vizitate.push_back(false);
		}

		int nr_componente_conexe = 0;
		for (int i = 0; i < nr_varfuri; i++)
		{
			if (!noduri_vizitate[i])
			{
				graph.DFScuListaDeNoduriVizitate(i, noduri_vizitate);
				nr_componente_conexe++;
			}

		}

		out_file << nr_componente_conexe;
		*/

}