Submission #1180983

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180983		stdfloat	Travelling Merchant (APIO17_merchant)	C++20	100 / 100	59 ms	1352 KiB

merchant

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int n;

void BF(vector<vector<ll>>& dis) {
	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++)
				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
		}
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	int m, K;
	cin >> n >> m >> K;

	vector<vector<int>> B(n, vector<int>(K)), S = B;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < K; j++)
			cin >> B[i][j] >> S[i][j];
	}

	vector<vector<ll>> dis(n, vector<ll>(n, (ll)1e18));
	while (m--) {
		int x, y, w;
		cin >> x >> y >> w; x--; y--;

		dis[x][y] = w;
	}

	BF(dis);

	vector<vector<int>> pr(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < K; k++)
				if (~B[i][k] && ~S[j][k]) pr[i][j] = max(pr[i][j], S[j][k] - B[i][k]);
		}
	}

	int l = 1, r = (int)1e9;
	while (l <= r) {
		int md = (l + r) >> 1;

		vector<vector<ll>> d(n, vector<ll>(n, (ll)1e18));
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++)
				d[i][j] = (ll)md * min((ll)1e18 / md, dis[i][j]) - pr[i][j];
		}

		BF(d);

		bool tr = false;
		for (int i = 0; i < n && !tr; i++)
			tr = d[i][i] <= 0;

		if (tr) l = md + 1;
		else r = md - 1;
	}

	cout << l - 1;
}

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