글 읽기 - 이 풀이방식의 어디가 틀린건지 잘 모르겠습니다

juhongkim2 6년 전 0

문제에서 입력받는대로 그래프를 만들고 벨만포드 알고리즘을 사용해서

dist[0]<0이면 possible을 출력하도록 했습니다

그런데 50퍼센트에서 틀리더군요...

제 생각으로는 벨만포드를 사용했을때(0에서 출발)

dist[0]<0이 되었다면 문제의 possible조건을 (무조건)만족 한다고 생각했습니다

왜냐하면 최단거리를 구하는 알고리즘이니까 0으로 다시 돌아오지 않는다면 dist[0]는 항상 0이 되어야 하니까 말이죠...

(다시 돌아오더라도 음수사이클이 형성되지 않으면 dist[0]는 0이 될테니까...)

이 풀이방법에 어떤 부분이 잘못된건가요?

#include <stdio.h>
#include <vector>
#include <algorithm>
#define INF 1000000000
using namespace std;

typedef struct{
	int from,to,cost;
}Edge;

bool operator<(Edge e1, Edge e2)
{
	if(e1.from<e2.from)
		return true;

	return false;
}

int T,N,M,dist[1001];
Edge e[2001];

int main()
{
	int test,i,j,A,B,C,negative_cycle;
	Edge in,out;

	scanf("%d",&T);

	for(test=1;test<=T;test++){
		scanf("%d %d",&N, &M);

		for(i=0;i<M;i++){
			scanf("%d %d %d",&A, &B, &C);

			in.from=A;
			in.to=B;
			in.cost=C;
			e[i]=in;
		}
		sort(e,e+M);

        //이부분 실수...그런데 i=0;i<N;i++으로 해도 틀립니다
        for(i=1;i<=N;i++){
			dist[i]=INF;
		}
		dist[0]=0;
		negative_cycle=0;

		for(i=1;i<=N;i++){
			for(j=0;j<M;j++){
				out=e[j];

				if(dist[out.from]!=INF && dist[out.to]>dist[out.from]+out.cost){
					dist[out.to]=dist[out.from]+out.cost;

					if(i==N)
						negative_cycle=1;
				}
			}
		}

		if(dist[0]<0)
			printf("Case #%d: possible\n",test);
		else
			printf("Case #%d: not possible\n",test);
	}

	return 0;
}

minjoonist 4년 전 0

2년 뒤지만 negative_cycle을 계산해놓고 안 쓰신것 같네요...

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

문제

문제

출처

ICPC

이 풀이방식의 어디가 틀린건지 잘 모르겠습니다

juhongkim2 6년 전 0

minjoonist 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말