14077 - Parada

번역

탱크 퍼레이드가 1번 도시에서 $N$번 도시까지 진행됩니다. 각 도로 $i$마다 몇 대의 탱크 $T_i$가 지나갈 수 있는지 알려져 있으며, 이 수를 넘으면 도로를 보수해야 합니다. 이후에는, 도로 수리 비용이 탱크 수에 따라 제곱으로 증가하며, 이는 $C_i*(T-T_i)^2$ 원입니다. 여기서 $C_i$는 도로 수리 비용의 계수입니다. 도로를 복구하는 데 사용할 수 있는 연간 예산 $K$원이 있습니다. $K$원을 넘지 않는 비용으로 얼마나 많은 탱크를 퍼레이드에 사용할 수 있는지 구하세요. 적어도 하나의 경로는 존재할 것이 보장됩니다.

step 1

퍼레이드에 $X$대의 탱크를 참여시킬 수 있는지 없는지를 구할 수 있다고 해봅시다. $X$대를 참여시킬 수 있을 때 $X-1$대도 참여시킬 수 있으므로 이 문제는 이분 탐색으로 해결할 수 있습니다.

step 2

퍼레이드에 $X$대의 탱크를 참여시킬 수 있는지 없는지는 다익스트라로 구할 수 있습니다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<set>
#include<vector>
#include<queue>
using namespace std;
vector<pair<long long int, pair<long long int, long long int>>> v[100100];
priority_queue<pair<long long int, long long int>> q;
long long int g[100100];
long long int M = 922337203685470000ll;
int main() {
	long long int n, m, x, i, j;
	scanf("%lld%lld%lld", &n, &m, &x);
	for (i = 1;i <= m;i++) {
		long long int xx, yy, zz, ww;
		scanf("%lld%lld%lld%lld", &xx, &yy, &zz, &ww);
		v[xx].push_back({ yy,{zz,ww} });
		v[yy].push_back({ xx,{zz,ww} });
	}
	long long int s = 0, e = 1000000;
	while (s < e) {
		long long int mi = (s + e) / 2 + 1;
		q.push({ 0,1 });
		for (i = 1;i <= n;i++) {
			g[i] = x+1;
		}
		g[1] = 0;
		while (q.size()) {
			long long int gg = -q.top().first, i = q.top().second;
			q.pop();
			if (gg != g[i]) continue;
			for (j = 0;j < v[i].size();j++) {
				long long int d = v[i][j].first, p = v[i][j].second.first, c = v[i][j].second.second;
				long long int gg = (mi <= c ? 0 : p * (mi - c) * (mi - c));
				if (g[i] + gg < g[d] && g[i] + gg <= x) {
					g[d] = g[i] + gg;
					q.push({ -g[d], d });
				}
			}
		}
		if (g[n] > x) e = mi - 1; else s = mi;
	}
	printf("%lld", s);
	return 0;
}