[백준] 1916번 : 최소비용 구하기 [C/C++]

#문제

1916번: 최소비용 구하기

https://www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

 

---

#접근방법

이 문제는 어제 푼 문제랑 똑같은 문제이다. 다익스트라 알고리즘으로 최단비용을 구하면 된다.

https://rujang.tistory.com/entry/%EB%B0%B1%EC%A4%80-1753%EB%B2%88-%EC%B5%9C%EB%8B%A8%EA%B2%BD%EB%A1%9C-CC

[백준] 1753번 : 최단경로 [C/C++]

반응형

---

#풀이

#include <stdio.h>
#include <vector>
#include <queue>
#define INF 987654321
using namespace std;

int node[1005][1005];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >pq;
int value[1005];

int main(){
	int n,m;
	int u,v,w;
	int start,end;
	
	scanf("%d %d",&n,&m);
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			node[i][j] = INF;
	
	for(int i=1;i<=n;i++){
		node[i][i] = 0;
		value[i] = INF;
	}
	
	for(int i=0;i<m;i++){
		scanf("%d %d %d",&u,&v,&w);
		if(node[u][v]>w)
		node[u][v] = w;
	}
	
	scanf("%d %d",&start,&end);
	
	value[start] = 0;
	
	pq.push(make_pair(0,start));
	
	while(!pq.empty()){
		int x = pq.top().first;
		int U = pq.top().second;
		pq.pop();
		
		for(int i=1;i<=n;i++){			
			int V = i;
			int W = node[U][i];
			
			if(W==INF) continue;
			
			if(x+W<value[V]){
				value[V] = x+W;
				pq.push(make_pair(x+W,V));
			}
		}
	}
	
	printf("%d",value[end]);
	
	return 0;
}

 

어제 푼 문제 1753번 최단경로 문제와 동일한 알고리즘을 사용한 코드이다.

 

하지만 이 문제는 최단경로 문제와 다르게 u, v, w에서 u, v가 동일한 입력값이 들어간다는 것이다.

 

최단경로 문제와 똑같은 코드를 돌리면 26%에서 시간초과가 걸리게 된다.

 

이를 해결하기 위해 vector<pair<int,int> > node[1005] 로 만들었던 배열에서 int node[1005][1005]로 이차원 배열 형태로 만들었고, node[u][v]>w 일때 node[u][v] = w를 작성하여서 중복된 선들을 최소비용인 선 하나로 만들어 주었다.

 

그리고 다익스트라 알고리즘을 돌리고 value[end]를 출력하면 정답이다.

---

#성능

---

#정리

해당 문제가 다익스트라 알고리즘을 사용한다는 것,

 

예외 처리를 하기 위해 중복된 선들을 최소비용인 선 하나로 만들어 주는 것,

 

예전에 풀었던 문제에서 아이디어를 얻어오면 쉽게 풀 수 있는 문제였다.

 

비슷한 유형의 문제를 많이 풀게되면 문제만 봐도 어떤 알고리즘을 써야할지 감이온다.