백준 1916 최소비용구하기(벨만포드 알고리즘)

 

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다.

 

이 문제는 원래 다익스트라로 풀어야 하지만 연습겸 벨만포드로 풀어보았습니다.

 

벨만포드 알고리즘 같은경우 음의 가중치가 있을때 다익스트라를 사용할 수 없으므로 그때 사용을 합니다.

 

이때 시간복잡도는 O(|V||E|) 만큼 소요되므로 사실 이문제의 입력 최대치를 넣으면 1억이 됩니다. 그래서 시간초과가 나지 않을까 했는데  찾아보니 요즘 컴퓨터는 1억번 반복은 1초안에 해결을 할 수 있으므로 시간초과가 나지 않고 문제가 풀립니다!

 

간략하게 알고리즘을 설명하면 V-1번의 반복동안 각 정점에서 연결된 정점으로 가는 비용을 완화(더적은 비용이 있으면 그비용으로 교체)시키면서 진행합니다.

벨만포드 알고리즘의 경우 음수사이클의 존재유무도 알려줄 수 있는데 V번째에서도 만약 이 완화과정이 진행되었다면 그 그래프는 음수사이클이 존재함을 나타냅니다. 

 

다음은 코드입니다.

 

 

#include <iostream>
#include <vector>

#define INF 987654321
using namespace std;

/* 
	벨만포트 알고리즘 
	마지막 V번에서도 완화가 되면 음수 사이클이 존재함을 알려준다.	
*/

int V,M; 
vector<pair<int, int> > v[1001];
int upper[1001]; 

int bellmanFord(int src) { 
	//시작점 제외 모든 정점까지의 최단거리 INF로 초기화 
	fill_n(upper, 1001, INF);
	upper[src] = 0;
	bool updated;
	for(int i = 0; i < V; i++) {
		updated = false;
		for(int j = 1; j <= V; j++)
			for(int k = 0; k < v[j].size(); k++) {
				int there = v[j][k].first;
				int cost = v[j][k].second;
				
				if(upper[there] > upper[j] + cost) { // 완화 성공 
					upper[there] = upper[j] + cost;
					updated = true;
				}
			}
			
		if(!updated) break; //모든 간선에 대해 완화가 실패할경우 break; 
	}
	if(updated) return 1; //음수 사이클이 존재 
	
	return 0;
}

int main(void) {
	//ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> V >> M;
	for(int i = 0; i < M; i++) {
		int a,b,c;
		cin >> a >> b >> c;
		v[a].push_back(make_pair(b, c));
	}
	int start, arrive; cin >> start >> arrive;
	if(!bellmanFord(start))
		cout<<upper[arrive];
	return 0;
}