글 읽기 - 오류를 못찾겠어요 ㅠㅠ

aqws11 8년 전 0

들어오는 길을 set에 저장해서 다익스트라를 돌려서 x에서 각 마을로 이동하는 거리를 구하고

마을에서 x로 이동하는 거리를 구하기 위해 set[i][j] 랑 set[j][i]를 바꿔서 다익스트라를 돌립니다.

x->마을 은 time[]에 저장하고

마을 -> x는 time2[]에 저장을 해서 이걸 더한후에 max를 출력하는데 왜 틀린지 잘 모르겠어요

#include <stdio.h>
#include <string.h>
#define INF 1000000001

int set[1001][1001];
int time[1001];
int time2[1001];
int visit[1001];

int f_max(int a, int b){
	if (a > b)
		return a;
	else
		return b;
}
int main(){
	int n, n_edge, goal;
	int i,j;
	int x, y, cost;
	int min;

	scanf("%d %d %d", &n, &n_edge, &goal);
	

	for (i = 1; i <= n; i++){
		for (j = 1; j <= n; j++){
			set[i][j] = 9999;
		}
		set[i][i] = 0;
	}

	for (i = 0; i < n_edge; i++){
		scanf("%d %d %d", &x, &y, &cost);
		set[x][y] = cost;
	}
	

	for (i = 1; i <= n; i++){
		time[i] = set[goal][i];
	}

	visit[goal] = -1;
	
	int pivot;

	for (i = 2; i <= n; i++){
		min = INF;
		for (j = 1; j <= n; j++){
			if (visit[j] == 0 && min > time[j]){
				pivot = j;
				min = time[j];
			}
		}
		visit[pivot] = -1;

		for (j = 1; j <= n; j++){
			if (time[j] > time[pivot] + set[pivot][j])
				time[j] = time[pivot] + set[pivot][j];
		}
	}

	int swap;
	memset(visit, 0, 1001); 

	for (i = 1; i <= n; i++){
		for (j = i; j <= n; j++){
			swap = set[i][j];
			set[i][j] = set[j][i];
			set[j][i] = swap;
		}
	}

	for (i = 1; i <= n; i++){
		time2[i] = set[goal][i];
	}
	visit[goal] = -1;


	for (i = 2; i <= n; i++){
		min = INF;
		for (j = 1; j <= n; j++){
			if (visit[j] == 0 && min >time2[j]){
				pivot = j;
				min = time2[j];
			}
		}
		visit[pivot] = -1;
		for (j = 1; j <= n; j++){
			if (time2[j] > time2[pivot] + set[pivot][j])
				time2[j] = time2[pivot] + set[pivot][j];
		}
	}

	int max = 0;

	for (i = 1; i <= n; i++){
		time[i] += time2[i];
		max = f_max(max, time[i]);
	}
	printf("%d", max);
	
	return 0;

}

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

문제

문제

출처

ICPC

오류를 못찾겠어요 ㅠㅠ

aqws11 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말