Submission #842171

#	Time	Username	Problem	Language	Result	Execution time	Memory
842171		Tob	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	81 ms	4332 KiB

merchant

#include <bits/stdc++.h>

#define ll long long
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef pair <ll, ll> pii;

const int N = 107, K = 1007;
const ll inf = 1e18;

int n, m, k;
ll b[N][K], s[N][K], d[N][N], pr[N][N], dis[N][N];

void Min(ll& x, ll y) {x = min(x, y);}
void Max(ll& x, ll y) {x = max(x, y);}

int main () {
	FIO;
	cin >> n >> m >> k;
	
	for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) d[i][j] = inf;
	for (int i = 1; i <= n; i++) {
		d[i][i] = 0;
		for (int j = 1; j <= k; j++) {
			cin >> b[i][j] >> s[i][j];
		}
	}
	for (int i = 1; i <= m; i++) {
		ll x, y, w; cin >> x >> y >> w;
		d[x][y] = w;
	}
	for (int ii = 1; ii <= n; ii++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				Min(d[i][j], d[i][ii] + d[ii][j]);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (d[i][j] == inf) continue;
			pr[i][j] = 0;
			for (int ii = 1; ii <= k; ii++) {
				if (b[i][ii] != -1 && s[j][ii] != -1) Max(pr[i][j], s[j][ii] - b[i][ii]);
			}
		}
	}
	ll lo = 0, hi = 1e9;
	while (lo < hi) {
		ll mid = (lo + hi + 1) / 2;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (d[i][j] == inf || i == j) dis[i][j] = inf;
				else dis[i][j] = -pr[i][j] + d[i][j] * mid;
			}
		}
		for (int ii = 1; ii <= n; ii++) {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					Min(dis[i][j], dis[i][ii] + dis[ii][j]);
				}
			}
		}
		int ok = 0;
		for (int i = 1; i <= n; i++) {
			ok |= (dis[i][i] <= 0);
		}
		if (ok) lo = mid;
		else hi = mid-1;
	}
	
	cout << lo << "\n";

	return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 21 / 21
• Subtask 3: 33 / 33
• Subtask 4: 34 / 34