#include<stdio.h>
#include<stdlib.h>
#include"Header.h"

graph *build_graph(int);
node *get_node(int, int);
void insert(graph *,int, int, int);

void dijkstra(graph *g, int *d, int start)
{
	bool *visit = (bool*)malloc(g->V*sizeof(bool));

	int i;

	for (i = 0; i < g->V; i++)
	{
		d[i] = INT_MAX;
		visit[i] = false;
	}

	d[start] = 0;
	visit[start] = true;

	node *p = g->array[start].head;
	while (p != NULL)
	{
		d[p->dest] = p->cost;
		p = p->next;
	}

	int nr = 1;
	int vfmin = INT_MAX;

	while (nr != g->V)
	{
		vfmin = INT_MAX;
		int index = 0;

		for (i = 0; i < g->V;i++)
		if (visit[i] == false && d[i] < vfmin)
		{
			vfmin = d[i];
			index = i;
		}

		visit[index] = true;

		p = g->array[index].head;

		while (p != NULL)
		{
			if (d[index] + p->cost < d[p->dest])
				d[p->dest] = d[index] + p->cost;
			p = p->next;
		}
		nr++;
	}
	free(visit);

}

void main()
{
	FILE *f = fopen("in.txt", "r");
	
	int V;
	fscanf(f, "%d", &V);

	graph *g = build_graph(V);

	int x, y, z;
	while (fscanf(f, "%d%d%d", &x, &y, &z) != EOF)
		insert(g, x, y, z);

	int *d = (int*)calloc(V, sizeof(int));
	int start = 0;

	dijkstra(g, d, start);

	int i;
	for (i = 0; i < g->V; i++)
	{
		printf("S=%d -> D=%d \t : %d\n", start, i, d[i]);
	}

	// system("pause");

}

graph *build_graph(int V)
{
	graph *g = (graph*)malloc(sizeof(graph));

	g->V = V;
	int i;

	g->array = (adj_list*)malloc(V*sizeof(adj_list));

	for (i = 0; i < V; i++)
		g->array[i].head = NULL;

	return g;
}

void insert(graph *g, int start, int end, int cost)
{
	node *temp = get_node(end, cost);
	temp->next=g->array[start].head;
	g->array[start].head = temp;

	temp = get_node(start, cost);
	temp->next = g->array[end].head;
	g->array[end].head = temp;

}

node *get_node(int dest, int cost)
{
	node *temp = (node*)malloc(sizeof(node));
	temp->dest = dest;
	temp->cost = cost;
	temp->next = NULL;
	return temp;
}