양방향 최단 경로

#pragma warning(disable:4996)
#include 
#include 
#include 

#define INF 30000
#define TRUE 1
#define FALSE 0
int n;
int m;
int s;
int **weight;
int *distance;
int *found;

void input()
{
	int x, y, value;
	for (int i = 0; i < m; i++)
	{
		scanf("%d %d %d", &x, &y, &value);
		weight[x][y] = value;
		weight[y][x] = value;
	}
	for (int i = 1; i < n; i++)
	{
		weight[i][i] = 0;
	}
}

int choose(int n)
{
	//현재 distance 배열에서 가장 작은 가중치 값이 위치하고 있는 
	//배열의 인덱스를 찾아 반환하는 함수
	int i, min, minpos;
	min = INF;
	minpos = 0;

	for (int i = 0; i < n; i++)
	{
		if (distance[i] < min && found[i] == FALSE)
		{
			min = distance[i];

			minpos = i;
		}
	}
	return minpos;
}
void shortest_path(int start, int n)
{
	int u;
	for (int i = 1; i < n; i++)
	{
		distance[i] = weight[start][i];
		found[i] = FALSE;
	}
	found[start] = TRUE;
	distance[start] = TRUE;

	for (int i = 1; i < n - 1; i++)
	{
		u = choose(n);
		found[u] = TRUE;
		for (int w = 1; w < n; w++)
		{
			if (distance[u] + weight[u][w] < distance[w])
			{
				distance[w] = distance[u] + weight[u][w];
			}
		}
	}
}
void main()
{
	scanf("%d %d %d", &n, &m, &s);
	n++;
	weight = (int**)malloc(sizeof(int*) * (n));
	distance = (int*)malloc(sizeof(int)*n);
	found = (int*)malloc(sizeof(int)*n);

	for (int i = 0; i < n; i++)
	{
		weight[i] = (int)malloc(sizeof(int) * (n));
	}
	for (int i = 0; i < n; i++)
	{
		distance[i] = INF;
		for (int j = 0; j < n; j++)
		{
			weight[i][j] = INF;
		}
	}

	input(s);
	shortest_path(s, n);
	
	for (int i = 1; i < n; i++)
	{
		if (i != s && distance[i] != INF)
		{
			printf("%d %d\n", i, distance[i]);
		}
	}




	//free 선언
	for (int i = 0; i < n; i++)
	{
		free(weight[i]);
	}
	free(weight);
	free(distance);
	free(found);
}