글 읽기 - 1516번 어디가 문제인걸까요..?

bgjun0204 4년 전 0

인접 배열이 아닌 (유사) 인접 리스트

Way와 nWay를 사용하였으며

일반적인 위상정렬 알고리즘을 사용했습니다

직접 만든 예제 넣어봐도 잘 나오고

게시판에 적힌 다른 분들 예제도 다 잘 나오는데

제출 시 "틀렸습니다"라고 나오네요..

#include<stdio.h>

#define MAX_N 500
int n,time[MAX_N+1],Way[MAX_N+1][MAX_N+1],nWay[MAX_N+1],cnt[MAX_N+1],build[MAX_N+1];

int queue[MAX_N+1],rear,front;
#define put(queue_data) (queue[rear++]=(queue_data))
#define get() (queue[front++])
#define is_empty_queue() (rear==front)
#define clear_queue() (rear=front=0)

int main(void)
{
	int i,j,a;

	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a);
		time[i]=a;
		while(1)
		{
			scanf("%d",&a);
			if(a==-1) break;
			Way[a][++nWay[a]]=i;
			cnt[i]++;
		}
	}

	for(i=1;i<=n;i++) if(cnt[i]==0) put(i),build[i]=time[i];
	while(!is_empty_queue())
	{
		i=get();
		for(j=1;j<=nWay[i];j++)
		{
			if(build[Way[i][j]]<build[i]+time[Way[i][j]])
			{
				build[Way[i][j]]=build[i]+time[Way[i][j]],cnt[Way[i][j]]--;
				if(cnt[Way[i][j]]==0) put(Way[i][j]);
			}
		}
	}
	for(i=1;i<=n;i++) printf("%d\n",build[i]);
	return 0;
}

opop20207 4년 전 12

반례입니다.

저랑 똑같은 실수 하셨네요

4
20 -1
10 -1
1 1 2 -1
1000 1 2 3 -1

wrong
20
10
21
1020

correct
20
10
21
1021

bgjun0204 4년 전 0

오! 반례 감사합니다ㅎㅎ

우선 풀던거풀고나서 다시 손대봐야겠습니다

(방금 알람보는법 알았네요ㅎㅎ)

bgjun0204 4년 전 0

와우 반례 감사합니다~

역시 디버그는 비주얼 스튜디오네요

jksk0115 4년 전 0

저도 이 반례덕분에 해결할 수 있었습니다. @

opop20207님 감사합니다. ㅎㅎ

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

문제

문제

출처

ICPC

1516번 어디가 문제인걸까요..?

bgjun0204 4년 전 0

opop20207 4년 전 12

bgjun0204 4년 전 0

bgjun0204 4년 전 0

jksk0115 4년 전 0

opop20207님 감사합니다. ㅎㅎ

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말