[PS] 타임머신, 웜홀 (벨만-포드 기초) / C++ (백준 11675, 1865번)

타임머신 (백준 11675번)

웜홀 (백준 1865번)

• 음수 간선을 포함한 그래프의 최단 거리 혹은 음수 사이클을 찾고 싶을 때, 사용하는 벨만-포드 알고리즘에 대해 공부할 수 있었다.
• 그래프에 음수 간선이 포함되어 있으면, 그리디하게 진행되는 다익스트라로는 최단 거리를 구할 수 없음. 플로이드 워셜은 가능은 하지만 $O(V^3)$이고, 벨만-포드는 $O(VE)$ 만에 해결할 수 있음

 

타임머신(11675)

• 벨만-포드 알고리즘을 구현만 하면 되는 기초 문제.
• 음수 사이클을 돌 때, 최악의 상황에서 -10,000을 500(최대 정점 수) x 6000(최대 간선 수)번 더할 수 있으므로 최대 -30억에 접근할 수 있도록 long long을 설정해줘야 됨

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

long long cost[501], compare[501];
vector<pair<pair<int, int>, int> > edges;

void bellmanford()
{
	int size = edges.size();
	for (int i = 0; i < size; i++) {
		int st = edges[i].first.first, en = edges[i].first.second, co = edges[i].second;
		if (cost[st] == 2e9)continue;
		if (cost[en] > cost[st] + co)cost[en] = cost[st] + co;
	}
	return;
}

int main()
{
	int n, m;
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		edges.push_back(make_pair(make_pair(a, b), c));
	}
	for (int i = 2; i <= n; i++)cost[i] = 2e9;
	for (int i = 1; i < n; i++)bellmanford();
	for (int i = 1; i <= n; i++)compare[i] = cost[i];
	bellmanford();
	for (int i = 1; i <= n; i++) {
		if (compare[i] != cost[i]) {
			printf("-1\n");
			return 0;
		}
	}
	for (int i = 2; i <= n; i++)printf("%lld\n", cost[i] == 2e9 ? -1 : cost[i]);
	return 0;
}

 

 

웜홀(1865)

• 벨만-포드 알고리즘의 기초 문제로 dfs로 풀어보려다 고생한 문제.
• edge 벡터에 저장 로직을 각 노드마다 엣지를 저장하도록 구현해서 벨만-포드 함수가 좀 더럽다.
  
  • 작동은 잘 한다는 점!
• 발상하기 좀 힘들었지만, 결론적으로 단순히 음수 사이클이 존재하는지 확인하는 문제였다.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int n, m, w;
int cost[501], compare[501];
vector<pair<int, int> > edge[501];

void Bellman_ford() {
	for (int i = 1; i <= n; i++) {
		if (cost[i] == 2e9)continue;
		int size = edge[i].size();
		for (int j = 0; j < size; j++) {
			int target = edge[i][j].first, c = edge[i][j].second;
			if (cost[target] > cost[i] + c) {
				cost[target] = cost[i] + c;
			}
		}
	}
	return;
}

int main()
{
	int t;
	scanf("%d", &t);
	for (; t >= 1; t--) {
		scanf("%d %d %d", &n, &m, &w);
		for (int i = 0; i < m; i++) {
			int a, b, c;
			scanf("%d %d %d", &a, &b, &c);
			edge[a].push_back(make_pair(b, c));
			edge[b].push_back(make_pair(a, c));
		}
		for (int i = 0; i < w; i++) {
			int a, b, c;
			scanf("%d %d %d", &a, &b, &c);
			edge[a].push_back(make_pair(b, -c));
		}
		int flag = 0;
		for (int j = 1; j <= n; j++) {
			cost[j] = 0;
		}
		for (int j = 1; j < n; j++)Bellman_ford();
		for (int j = 1; j <= n; j++)compare[j] = cost[j];
		Bellman_ford();
		for (int j = 1; j <= n; j++) {
			if (compare[j] != cost[j])flag = 1;
		}
		if (flag)printf("YES\n");
		else printf("NO\n");
		for (int i = 1; i <= n; i++)edge[i].clear();
	}
	return 0;
}