[BOJ]백준 1939번: 중량제한(C++)/Dijkstra, Binary Search

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

1939번: 중량제한

이진탐색+그래프탐색 문제

건널 수 있는 최대 중량(중량의 범위)을 알아내는 것이기 때문에 해당 범위를 binary search로 찾아내야하고, 처음에는 DFS로 돌렸으나 메모리초과가 뜨길래

왜틀렸지?하고 질문게시판을 뒤져본 결과

"인접 행렬로 연결 상태를 저장하면 메모리가 터지기 때문에 인접 리스트로 구현해야 한다"는 것을 알았다

 

사실 그래프 탐색 알고리즘 자체는 어떤 것을 사용해도 solve 가능하다고 한다(DFS, BFS, Dijkstra 등등)

이 문제에서는 path만 존재한다면 OK이기 때문에 괜찮지만, 만약 cost까지 고려해야 한다면 multiple edge에 대한 처리를 해주어야 하기에 다익스트라가 더 적절할 것 같다 !!

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define pii pair<int,int>
#define INF 10000000000005
using namespace std;

int n, m,s,f;
vector<vector<pii>> g;

int main() {
	scanf("%d%d", &n, &m);
	g = vector<vector<pii>>(n + 1);

	for (int i = 0,u,v,w; i < m; i++) {
		scanf("%d%d%d", &u, &v, &w);
		g[u].push_back(make_pair(w, v));
		g[v].push_back(make_pair(w, u));
	}
	scanf("%d%d", &s, &f);

	int left = 0, right = 1000000001;
	while (left + 1 < right) {
		int mid = (left + right) / 2;

		priority_queue<pair<long long, int>> pq;
		vector<long long> dist(n + 1, INF);
		bool visit[10005] = { false };
		
		pq.push(make_pair(0, s));
		dist[s] = 0;

		while (!pq.empty()) {
			auto cur = pq.top().second; pq.pop();
			if (visit[cur])continue;

			visit[cur] = true;
			for (auto x : g[cur]) {
				if (!visit[x.second] && x.first >= mid && dist[x.second] > dist[cur] + x.first) {
					dist[x.second] = dist[cur] + x.first;
					pq.push(make_pair(-dist[x.second], x.second));
				}
			}
		}

		if (dist[f] != INF)left = mid;
		else right = mid;
	}

	printf("%d", left);
	return 0;
}