글 읽기 - 1504 - 다익스트라 틀린 이유 질문드려요

gskohot72 4년 전 0

다익스트라를 3번 돌려서,

start -> v1 -> v2 -> end

start -> v2 -> v1 -> end

중 최소값을 출력하는 방식으로 짰는데, 계속 틀리네요...

대부분 C++ 큐 이용해서 코딩하셔서 모범답안이 잘 참고가 안되는군요

틀린 부분 지적 부탁드립니다!

#include <stdio.h>
#include <string.h>
#define MAX 801
#define INF 800000

int v, e;
int vtx1, vtx2;
int G[MAX][MAX];
long long D[MAX];
int visit[MAX];

void initGraph(){
	scanf("%d %d", &v, &e);
	int v1, v2, w;
	
	for (int i=1 ; i<=v ; i++){
		for (int j=1 ; j<=v ; j++){
			if (i==j) G[i][j] = 0;
			else G[i][j] = INF;
		}
	}
	
	for (int i=0 ; i<e ; i++){
		scanf("%d %d %d", &v1, &v2, &w);
		G[v1][v2] = w;
		G[v2][v1] = w;
	}
	
	scanf("%d %d", &vtx1, &vtx2);
}

void dijk(int s){
	memset(D, 0, sizeof(D));
	memset(visit, 0, sizeof(visit));
	
	for (int i=1 ; i<=v ; i++){
		D[i] = G[s][i];
	}
	visit[s] = 1;
	
	for (int i=1 ; i<=v ; i++){
		int minI = 0;
		long long minV = INF;
		for (int j=1 ; j<=v ; j++){
			if (!visit[j] && D[j] < minV){
				minI = j;
				minV = D[j];
			}
		}
		visit[minV] = 1;
		
		
		for (int j=1 ; j<=v ; j++){
			if (visit[minV]) continue;
			if (D[minI] + G[minI][j] < D[j]){
				D[j] = D[minI] + G[minI][j];
			}
		}
	
	}
	
}


int main(){
	initGraph();
	// s=1 , N=v
	dijk(1);
	long long one_vtx1 = D[vtx1];
	long long one_vtx2 = D[vtx2];

	dijk(vtx1);
	long long vtx1_vtx2 = D[vtx2];

	dijk(v);
	long long N_vtx1 = D[vtx1];
	long long N_vtx2 = D[vtx2];
	
	long long one_vtx1_vtx2_N = one_vtx1 + vtx1_vtx2 + N_vtx2;
	long long one_vtx2_vtx1_N = one_vtx2 + vtx1_vtx2 + N_vtx1;
	

	if (one_vtx1_vtx2_N > INF && one_vtx2_vtx1_N > INF){
		printf("-1");
		return 0;
	}
	
	long long res = (one_vtx1_vtx2_N < one_vtx2_vtx1_N) ? one_vtx1_vtx2_N : one_vtx2_vtx1_N;
	printf("%lld", res);
	
	return 0;
}

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

문제

문제

출처

ICPC

1504 - 다익스트라 틀린 이유 질문드려요

gskohot72 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말