#include <stdio.h>
#include <vector>
#include <algorithm>

#define MAX 1000

struct Node{
	int n, weight;
}node; //struct untuk deklarasi type 'node' sehingga dapat memiliki attribut suatu titik

int flag[MAX], previ[MAX], dist[MAX], vertex, source, destination;
int graph[MAX][MAX];

std::vector <Node> vec_nodes;

void add(int N, int cost){
	node.n = N;
	node.weight = cost;
	vec_nodes.push_back(node);
}

bool data_sort(Node a, Node b){
	return a.weight < b.weight;
}

void UCS(){
	for(int i = 1; i <= vertex; i++){ //Initiate value tiap penyimpanan
		flag[i] = 0;
		dist[i] = 10e9;
		previ[i] = -1;
	}
	dist[source] = 0; //Value untuk source node (35 - 38)
	previ[source] = -1;
	add(source, 0);

	while(!vec_nodes.empty()){
		int u = vec_nodes[0].n;
		vec_nodes.erase(vec_nodes.begin());
		for(int i = 1; i <= vertex; i++){
			if(graph[u][i] != 0 && flag[i] == 0){ //Node u dan i terhubung langsung oleh 1 garis
				if(dist[u] + graph[u][i] < dist[i]){ //Kondisi untuk jika jaraknya lebih kecil maka kemungkinan akan menjadi hasil final
					dist[i] = dist[u] + graph[u][i];
					previ[i] = u;
				}
				add(i, dist[i]); //Add node i ke vector yang menyimpan jaraknya
				sort(vec_nodes.begin(), vec_nodes.end(), data_sort); //Vector diurutkan sesuai prinsip UCS yang mengambil node dengan jarak terpendek dari root
			}
		}
		flag[u] = -1; //Tanda bahwa titik tsb sudah ditemukan
	}
}

void printPath(int destination){
	if(destination == source)
		printf("%d ", source);
	else if(previ[destination] == -1)
		return;
	else{
		printPath(previ[destination]);
		printf("%d ", destination);
	}
}

void printDistance(){
	int i;
	printf("\nDistance Measurement:\n");
	for(i = 1; i <= vertex; ++i){
		printf("%d -> %d = %d \n", source, i, dist[i]);
	}
	printf("\n");
}

int main(){
	int edges, u, v, w;
	printf("Enter number of edges: "); //Jumlah garis
	scanf("%d", &edges);
	vertex = -1;
	printf("Enter %d edges (from-to-distance) each separated by a space:\n", edges);
	for(int i = 0; i < edges; i++){ //Buat input data graf
		scanf("%d %d %d", &u, &v, &w);
		graph[u][v] = w;
		vertex = std::max(u, std::max(v, vertex)); //Buat nyari jumlah vertex
	}
	printf("Enter source and destination: ");
	scanf("%d %d", &source, &destination);
	UCS(); //Algoritma utama Uniform-cost search
	printDistance(); //Jarak terpendek source node ke semua titik

	printf("The path from %d to %d is given below : \n", source, destination);
	printPath(destination); //Untuk print jalur source node ke target node

	return 0;
}