글 읽기 - 플로이드문제 fill함수를 잘못 사용한건가요??

nacean 3년 전 0

fill(dist[0], dist[100], INT_MAX);

for (int i = 1; i <= town; i++)

{

dist[i][i] = 0;

}

이부분을

for (int i = 1; i <= town; i++)
{
for (int j = 1; j <= town; j++)
{
if (i == j)
dist[i][j] = 0;
else
dist[i][j] = INT_MAX;
}
}

이렇게 바꾸니 맞다고 정답은 나왔는데

fill함수 사용법이 잘못 된건가요??

위 코드로 예제는 잘 나왔는데...

이것때문에 1시간동안 뻘짓했네요...

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <limits.h>

using namespace std;

int dist[101][101]; // 정점에서 정점까지 비용

void floyd_warshall(int town)
{
	for (int a = 1; a <= town; a++) // 거쳐가는 노선
	{
		for (int start = 1; start <= town; start++) // 거쳐가는것 이전 노선
		{
			for (int stop = 1; stop <= town; stop++)
			{
				if (dist[start][a] != INT_MAX && dist[a][stop] != INT_MAX)
				{
					if (dist[start][a] + dist[a][stop] < dist[start][stop])
					{
						dist[start][stop] = dist[start][a] + dist[a][stop];
					}
				}
			}
		}
	}

	for (int start = 1; start <= town; start++)
	{
		for (int stop = 1; stop <= town; stop++)
		{
			if (dist[start][stop] == INT_MAX)
				printf("0 ");
			else
				printf("%d ", dist[start][stop]);
		}
		printf("\n");
	}
}


//줄 정리 단축키 : ctrl K + F
//주석처리 단축키 : ctrl K + C,    ctrl K + U
int main()
{
	int town;
	scanf("%d", &town);

	int bus;
	scanf("%d", &bus);

	fill(dist[0], dist[100], INT_MAX);

	for (int i = 1; i <= town; i++)
	{
		dist[i][i] = 0;
	}


	for (int i = 0; i < bus; i++)
	{
		int start, stop, weight;
		scanf("%d %d %d", &start, &stop, &weight);

		if(dist[start][stop] > weight)
		dist[start][stop] = weight;
	}

	floyd_warshall(town);

	return 0;
}

byeongkeunahn 3년 전 1

Off-by-one error입니다. dist[0]부터 dist[100]까지 fill()을 호출하면 dist[0][0], dist[0][1], ..., dist[99][0], ..., dist[99][100]까지 채워집니다.

-> Correct statement: fill(dist[0], dist[101], INT_MAX).

nacean 3년 전 0

아 감사합니다 ㅜㅜㅜㅜ 배열 크기를 잘못 생각했네요...

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

문제

문제

출처

ICPC

플로이드문제 fill함수를 잘못 사용한건가요??

nacean 3년 전 0

byeongkeunahn 3년 전 1

nacean 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말