[백준] 24024번 - 삼색 그래프

문제

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

 

풀이

X개 이하의 스푼을 사용했을 때, 최소 비용의 최대 값을 구해야 함

조금 생각해보면, X 스푼을 사용했을 때가 최소 비용의 최대 값임을 알 수 있다.

정확한 그래프 개형은 몰라도, 특정 값에서 최대가 되는 그래프를 그리기 때문에, 빨간색 면에 대해 n 스푼, 파란색 면에 대해 X-n 스푼으로 삼분 탐색을 돌려주면 된다.

 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <map>
#include <cstring>
#include <cmath>
#include <string>
using namespace std;
int N, M, X;
struct Input {
	int n;
	long long cost;
	int color;
};
struct Node {
	int n;
	long long cost;
	bool operator<(const Node& o) const {
		return cost > o.cost;
	}
};
priority_queue<Node> pq;
vector<Input> graph[200001];
long long answer[200001];
long long dijkstra(long long red, long long blue)
{
	for (int i = 1; i <= N; ++i) {
		answer[i] = 1000000000000000;
	}
	pq.push({1, 0});
	answer[1] = 0;
	while (!pq.empty())
	{
		Node now = pq.top();
		pq.pop();
		if (now.cost > answer[now.n])continue;
		for (int i = 0; i < graph[now.n].size(); ++i) {
			Input nxt = graph[now.n][i];
			long long nxtCost = nxt.cost + answer[now.n];
			if (nxt.color == 1) {
				nxtCost = nxtCost + red;
			}
			else if (nxt.color == 2) {
				nxtCost = nxtCost + blue;
			}
			if (nxtCost < answer[nxt.n]) {
				answer[nxt.n] = nxtCost;
				pq.push({ nxt.n, nxtCost });
			}
		}
	}
	return answer[N];
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> M >> X;
	long long ia, ib, ic, id;
	for (int i = 0; i < M; ++i) {
		//U V W P
		//a,b를 연결, w, 색 p 검 빨 파
		cin >> ia >> ib >> ic >> id;
		graph[ia].push_back({ (int)ib, ic, (int)id });
		graph[ib].push_back({(int)ia, ic, (int)id});
	}
	//1 ~ N;
	if (X < 3) {
		long long ans = -1;
		for (int i = 0; i <= X; ++i) {
			ans = max(ans, dijkstra(i, X - i));
		}
		cout << ans;
		return 0;
	}

	long long left = 0;
	long long right = X;
	//cout << dijkstra(0) << ", " << dijkstra(X) << ".\n";
	//for (int i = 0; i <= X; ++i) dijkstra(i);
	while (right - left >= 3) {
		long long lm = (left * 2 + right) / 3;
		long long rm = (right * 2 + left) / 3;
		if (dijkstra(lm, X - lm) < dijkstra(rm, X - rm)) {
			left = lm;
		}
		else {
			right = rm;
		}
	}
	long long ans = -1;
	for (int i = 0; i < 3; ++i) {
		long long curr = left + i;
		ans = max(ans, dijkstra(curr, X - curr));
	}
	cout << ans;
	return 0;
}