글 읽기 - 틀렸습니다 뜨는데 도저히 모르겠습니다.

dlwnsxo98 3년 전 1

알고리즘은 모든 간선의 가중치를 2배를 해서 받습니다.(짝수 만들기)

GH간선만 2배의 -1을 해줘서 홀수로 세팅합니다.

그상태에서 다익스트라 알고리즘으로 시작점에서 각 노드까지 최단거리를 얻습니다.

최단거리 중 홀수인 목적지를 후보 목적지에서 정렬하여 출력합니다.

도와주시면 감사하겠습니다!

#include <stdio.h>
#define INF		( 10000 )
int N, M, T;	// node 개수 / 간선 개수 / 도착 후보지 개수 
int S, G, H;	// 시작 노드 / g-h 꼭 지나가는 곳

// Sol2) GH간선만 홀수로 만들어줘서 최단경로중 홀수인 것은 GH를 지났다고 판정해서 출력! 
int st_dist[2100];		// 각 노드까지 최단거리 저장(다익스트라의 결과물) 시작점부터
int visit[2100];	// 탐색 했는지 확인 visit 
int w[2100][2100];	// 길 input 가중치 저장 
int nom[110];		// 목적지 후보자들 

int getSmallIndex ( int *dist )
{
	int i, result = -1;
	int min = INF+10;
	for ( i = 1; i <= N; i++ ) {
		if ( visit[i] == 1 )	continue;
		if ( min > dist[i] ) {
			min = dist[i];
			result = i;
		}
	}
	
	return result;
}
void Dijkstra ( int st, int *dist )
{
	int i, j;
	for ( i = 1; i < 2100; i++ )	visit[i] = 0;		// visit 초기화 
	for ( i = 1; i <= N; i++ )	dist[i] = w[st][i];		// 첫번째 노드 대입
	visit[st] = 1;
	
	for ( i = 1; i <= N-1; i++ ) {	// 첫 점은 위에서 했고, 마지막점은 해도 결과가 바뀌지 않는다. 따라서 -2 
		int cur = getSmallIndex(dist);
		if ( cur == -1 )	break;
		visit[cur] = 1;
		for ( j = 1; j <= N; j++ ) {
			if ( visit[j] == 1 )	continue;
			if ( dist[j] > dist[cur] + w[cur][j] )	dist[j] = dist[cur] + w[cur][j];
		}
	}
	
} 
int main ( void )
{
	int TEST_CASE, Ti;
	scanf("%d", &TEST_CASE);
	for ( Ti = 1; Ti <= TEST_CASE; Ti++ ) {
		int i, j;
		scanf("%d %d %d", &N, &M, &T);
		scanf("%d %d %d", &S, &G, &H);
		for ( i = 0; i < 2100; i++ ) {
			for ( j = 0; j < 2100; j++ )	{
				w[i][j] = INF;					// 가중치 그래프 9999로 초기화 
				if ( i == j )	w[i][j] = 0;
			}
		}
		for ( i = 1; i <= M; i++ ) {
			int s, e, we;
			scanf("%d %d %d", &s, &e, &we);
			w[s][e] = 2 * we; 	w[e][s] = 2 * we;		// 가중치 그래프 input 받기(양방향)
			if ( ( s == G && e == H ) || ( s == H && e == G ) ) {
				w[s][e] -= 1; 	w[e][s] -= 1;		// GH만 홀수로 만들기 
			}
		}
		for ( i = 1; i <= T; i++ ) {
			scanf("%d", &nom[i]);			// 도착지 후보자 input 받기 
		}
		
		Dijkstra(S, st_dist);
		int answer[110];
		int cnt = 0;
		
		for ( i = 1; i <= T; i++ ) {
			if ( st_dist[nom[i]] % 2 == 1 ) answer[++cnt] = nom[i];
		}
		for ( i = 1; i < cnt; i++ ) {
			for ( j = i+1; j <= cnt; j++ ) {
				if ( answer[i] > answer[j] ) {
					int tmp = answer[i];
					answer[i] = answer[j];
					answer[j] = tmp;
				}
			}
		}
		for ( i = 1; i <= cnt; i++ )	printf("%d ", answer[i]);
		printf("\n");
	}
	
	return 0;
} 

djm03178 3년 전 1

INF가 10000인 것이 너무 작습니다. 간선을 여러 개 거치다 보면 최단경로가 10000보다 훨씬 커질 수 있습니다.

dlwnsxo98 3년 전 0

감사합니다. INF값만 20억으로 고치니 맞았네요^^

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

문제

문제

출처

ICPC

틀렸습니다 뜨는데 도저히 모르겠습니다.

dlwnsxo98 3년 전 1

djm03178 3년 전 1

dlwnsxo98 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말