PTA - 09 - 최소 생 성 트 리 도로 마을 통 Prime 알고리즘 (c 언어)

13976 단어 해제데이터 구조
09 - 최소 생 성 나무 도로 마을 통 (30 분)
기 존의 마을 간 도로 에 대한 통계 데이터 표 에는 표준 도로 로 건설 할 수 있 는 몇 개의 도로 의 원가 가 열거 되 어 있 으 며, 모든 마을 이 도로 연결 에 필요 한 최저 원 가 를 가지 도록 한다.
입력 형식: 입력 데 이 터 는 도시 수 정수 N (≤ 1000) 과 후보 도로 수 목 M (≤ 3N) 을 포함한다.그 다음 에 M 행 은 M 개의 도로 에 대응 하여 각 줄 에 3 개의 정 수 를 주 었 는데 그것 이 바로 이 도로 가 직접 연 결 된 두 도시 의 번호 와 이 도로 개축 의 예산 비용 이다.간단하게 말하자면, 도 시 는 1 부터 N 까지 번호 가 있다.
출력 형식: 마을 통 에 필요 한 최저 비용 을 출력 합 니 다.입력 데이터 가 원활 하지 못 하면 출력 - 1 은 더 많은 도 로 를 건설 해 야 한 다 는 뜻 이다.
입력 예시:
6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3

출력 예시:
12

코드 는 다음 과 같 습 니 다:
#include
#include
int map[1001][1001];
int minCost[1001];//               
int visited[1001];
int N,M;
int min(int a,int b)
{
	return a > b ? b : a;
}
int prime()
{
	int i,sum=0,v;
	for(i=1;i<=N;i++) 
		minCost[i]=99999999;//      
	minCost[1]=0;
	while(1)
	{
		v = -1;
		for(i=1;i<=N;i++)//              
		{
			if(!visited[i]&&(v==-1||minCost[v]>minCost[i]))
				v = i;
		}
		if(v==-1)
			break;//          
		if(minCost[v]==99999999)
			return 0;//        ，       ，         		
		visited[v]=1;
		sum+=minCost[v];
		for(i=1;i<=N;i++)
		{
			if(map[v][i])
				minCost[i]=min(minCost[i],map[v][i]);//                
		}
	}
	for(i=1;i<=N;i++)
	{
		if(!visited[i])
			return 0;
	}
	return sum;
} 
int main()
{
	int i;
	int city1,city2,cost;
	scanf("%d %d",&N,&M);
	for(i=0;i<M;i++)
	{
		scanf("%d %d %d",&city1,&city2,&cost);
		map[city1][city2]=cost;// 0        
		map[city2][city1]=cost;
	}
	int sum = prime();
	if(sum)
		printf("%d
",sum);
	else
		printf("-1
");
	return 0;
}
Solidjs를 사용한 멋진 양식
[스파르타코딩클럽] 웹개발 종합반 4주차 숙제

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage