글 읽기 - 어느부분이 틀렸을까요?

qktlf789456 3년 전 0

감이 잘 안오네요 맞게한거같은데 뭐가틀렸을지싶네요..

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>




/*
4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0
*/

int size;
int** matrix;


int final_result = 0;
int last_node = -1;

int count = 0;

char* connected;

void prim(int startIdx)
{
	connected[startIdx] = 1;

	

	while (1)
	{
		int from_idx = -1;
		int min_idx = -1;
		int min_value = 99999999;
		for (int i = 0; i < size; i++)
		{
			if (connected[i] == 1)
			{
				from_idx = i;

				for (int j = 0; j < size; j++)
				{
					if (matrix[i][j] && connected[j] == 0 && matrix[i][j] < min_value)
					{
						from_idx = i;
						min_idx = j;
						min_value = matrix[i][j];
					}
				}
			}
		}

		if (min_idx == -1)
			break;

		count++;

		//printf("[%d] --(%d)--> [%d]\n", from_idx, matrix[from_idx][min_idx], min_idx);
		
		last_node = min_idx;


		final_result += min_value;

		connected[from_idx]++;
		connected[min_idx] = 1;
	}


}


void initialize()
{
	for (int i = 0; i < size; i++)
		connected[i] = 0;
	final_result = 0;
	last_node = -1;
	count = 0;
}

int main()
{
	scanf("%d", &size);
	matrix = (int**)malloc(sizeof(int*) * size);


	connected = (char*)malloc(size);

	for (int i = 0; i < size; i++)
	{
		connected[i] = 0;
		matrix[i] = (int*)malloc(sizeof(int) * size);
		for (int j = 0; j < size; j++)
		{
			scanf("%d", &matrix[i][j]);
		}
	}

	
	int output_result = 99999999;
	for (int i = 0; i < size; i++)
	{
		//printf("\n\n\n\n");
		prim(i);


		
		//("[%d] --(%d)--> [%d]\n", last_node, matrix[last_node][i], i);
		if(count == size -1)
		output_result = final_result + matrix[last_node][i] < output_result ? final_result + matrix[last_node][i] : output_result;


		initialize();
	}
	printf("%d", output_result);


	return 0;	
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어느부분이 틀렸을까요?

qktlf789456 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말