글 읽기 - 1197번 최소 스패닝 트리 문제 뭐가 문제일까요?

choidek 6년 전 0

최소 스패닝 트리에서 최소 비용을 구하는 문제인데 9% 대에서 계속 런타임 에러가 뜹니다.

뭐가 문제일까요?

#include <stdio.h>

#define INF 1000000

int n, m;
int mat[10001][10001];
long long int cost;
int visited[10001];
int dist[10001];

void prim(void);

int main()
{
	int i, j;
	int u, v, w;
	scanf("%d %d", &n, &m);
    
    for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= n; j++)
			mat[i][j] = INF;
	}
    
	i = 0; 
	while (i < m)
	{
		scanf("%d %d %d", &u, &v, &w);
		if(mat[u][v] > w) mat[u][v] = w;
		i++;
	}

    prim();
    printf("%lld", cost);

	return 0;
}

void prim(void)
{
	int i;
	int close_node;
	int count;
	long long min;
	

	for (i = 1; i <= n; i++)
		dist[i] = INF;

	count = 0;
	dist[1] = 0;
	while (count < n)
	{
		min = INF;
		close_node = -1;

		for (i = 1; i <= n; i++)
		{
			if (!visited[i])
			{
				if (min < dist[i])
				{
					min = dist[i];
					close_node = i;
				}
			}
		}

		for (i = 1; i <= n; i++)
		{
			if (!visited[i] && mat[close_node][i] != INF)
			{
				if (mat[close_node][i] < dist[i])
					dist[i] = mat[close_node][i];
			}
		}

		cost = cost + min;
		visited[close_node] = 1;
		count++;
	}
}

ehddml3 6년 전 0

캡처.PNG

"그래프 인접리스트"를 검색해보세요

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

문제

문제

출처

ICPC

1197번 최소 스패닝 트리 문제 뭐가 문제일까요?

choidek 6년 전 0

ehddml3 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말