글 읽기 - 삼각 그래프 질문 입니다..

semtax 8년 전 0

틀리는 케이스를 알려주시면 감사하겠습니다..

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define MAX 100010

int N,K;
long long int graph[MAX][3];
long long int dist[MAX][3];

int main() {

	while(1)
	{
		scanf("%d",&N);
		
		if(N==0)
			break;
		
		memset(dist,0,sizeof(dist));
		memset(graph,0,sizeof(graph));
		
		for(int i=0;i<N;i++)
			scanf("%lld %lld %lld",&graph[i][0],&graph[i][1],&graph[i][2]);
		
		for(int i=0;i<3;i++)
			dist[0][i] = graph[0][i];
		
		dist[0][2] = dist[0][1] + graph[0][2];
		dist[1][0] = dist[0][1] + graph[1][0];
		dist[1][1] = min(dist[1][0],dist[0][1]) + graph[1][1];
		dist[1][2] = min(min(dist[0][1],dist[0][2]),dist[1][1]) + graph[1][2];
		
		for(int i=1;i<N;i++)
		{			
			
			dist[i][0] = min(dist[i-1][0],dist[i-1][1]) + graph[i][0];
			dist[i][1] = min(min(min(dist[i-1][0],dist[i-1][1]),dist[i-1][2]),dist[i][0]) + graph[i][1];
			dist[i][2] = min(min(dist[i-1][1],dist[i-1][2]),dist[i][1]) + graph[i][2];
			
		}
	
		printf("%d. %lld\n",K+1,dist[N-1][1]);
		K++;
	}
	
	return 0;
}

f52985 8년 전 1

-1 0 0

0 0 0

정답 : 0

출력 : -1

for문을 돌 때 인덱스 i를 1부터 시작하면서, dist[1][1]에 불가능한 경로의 값이 덮어 씌워지네요

semtax 8년 전 0

감사합니다

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

문제

문제

출처

ICPC

삼각 그래프 질문 입니다..

semtax 8년 전 0

f52985 8년 전 1

semtax 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말