글 읽기 - 9%에서 틀렸습니다.

yepp0112 3년 전 1

해당 소스를 저렇게 짰는데 주석 보고 이해 되시련지 모르겠어요ㅠㅠ

저렇게 짜봤는데 9%에서 틀렸습니다 나오네요ㅠㅠㅠㅠ

분명 프림알고리즘이 제가 생각한게 맞다면 저 코드로도 정답이 나와야할텐데

혹시 특별한 반례가 존재할까요...??

알고리즘 고수님들 반례 부탁드립니다ㅠㅠㅠㅠㅠ

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

int visit[10001];

//long long int arr[10001][10001];

int main (){
	int v1,e;
	
	scanf("%d %d",&v1,&e);
	
	int i;
	
	vector<int> v[v1+1];
	vector<long long int> vv[v1+1];
	for(i=0;i<e;i++){
		int a,b,c;
		
		scanf("%d %d %d",&a,&b,&c);
		
		v[a].push_back(b);
		v[b].push_back(a);
		
		vv[a].push_back(c); // 가중치 저장 a->b
		vv[b].push_back(c); // 가중치 저장 b->a
		//arr[a][b]=c;
		//arr[b][a]=c;
	}
	
	visit[1]=1;
	
	int start=1;
	
	long long int sum=0;
	
	for(i=0;i<v1-1;i++){
		int j;
		
		long long int gamin=2147483648;
		
		int min;
		
		for(j=0;j<v[start].size();j++){
			if(visit[v[start][j]]==1) continue; // 방문한 노드면 건너뜀 
			
			if(gamin>vv[start][j]){ // 시작점에서 종점으로 가는 가중치중 최소값 찾기 
				gamin=vv[start][j];
				min=v[start][j];
			}
		}
		
		//printf("min : %d, gamin : %d\n",min,gamin);
		
		sum+=gamin; // 가중치는 더함 
		
		visit[min]=1; // 목적지 정점을 방문한 노드로 변환 
		
		start=min; // 다시 목적지 정점을 시작 정점으로 
	}
	
	printf("%lld",sum);
	return 0;
}

qktlf789456 3년 전 2

A -> B = 2

A -> C = 3

B -> C = 9999

이렇게 INPUT이 되어 있는경우

답이 5와는 다르게

10001 이 출력될 것 같습니다.

start=min; 이부분이 잘못되었어요

yepp0112 3년 전 1

감사합니다. 덕분에 해결했습니다.ㅎㅎ

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

문제

문제

출처

ICPC

9%에서 틀렸습니다.

yepp0112 3년 전 1

qktlf789456 3년 전 2

yepp0112 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말