글 읽기 - 반례 좀 찾아 주세요..

piri007 5년 전 0

dp를 이용해서 만들었습니다.

#include <stdio.h>
#include <algorithm>

#define ma 1000000000

using namespace std;

int m, start;
int bus[101][101] = {};
int cache[101][101] = {};

int dp(int s, int f);

int main()
{
	int n;
	scanf("%d %d", &m, &n);

	for (int i = 1; i <= n; i++)
	{
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		if (bus[a][b])
			bus[a][b] = min(c, bus[a][b]);
		else
			bus[a][b] = c;
	}

	for (int i = 1; i <= m; i++)
	{
		printf("\n");
		for (int j = 1; j <= m; j++)
		{
			start = i;
			if (dp(i, j) == ma)
				printf("0 ");
			else printf("%d ", dp(i, j));
		}
	}
}

int dp(int s, int f)
{
	if (cache[s][f])
		return cache[s][f];

	if (s == f)
		return cache[s][f] = 0;

	int mini = 1000000000, check = 0;
	for (int i = 1; i <= m; i++)
	{
		if (bus[s][i])
		{
			int money = bus[s][i];
			bus[s][i] = 0;
			mini= min(dp(i, f) + money,mini);
			bus[s][i] = money;
			check = 1;
		}
	}
	if (check)
		return cache[s][f] = mini;


	return ma;
}

djm03178 5년 전 0

문제 이름부터가 플로이드인데, 굳이 플로이드 알고리즘을 안 쓰고 다르게 푸시는 이유를 모르겠습니다.

piri007 5년 전 0

dp연습하려고 풀었는데, 아무리 생각해도 틀린 이유를 모르겠어요.

uytr083 5년 전 0

dp로 푸는 문제는 사이클이 생기면 안 되는데 이건 사이클이 생길 수 있으니 dp로 못 푼다고 생각합니다.

piri007 5년 전 0

같은 버스를 한번만 탈 수 있도록 만들어 사이클을 방지하였습니다.

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

문제

문제

출처

ICPC

반례 좀 찾아 주세요..

piri007 5년 전 0

djm03178 5년 전 0

piri007 5년 전 0

uytr083 5년 전 0

piri007 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말