Submission #1180978

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180978		stdfloat	Travelling Merchant (APIO17_merchant)	C++20	0 / 100	57 ms	2112 KiB

merchant

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

using ll = long long;

#define int long long

int n;

void BF(vector<vector<int>>& 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]);
		}
	}
}

int32_t 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<int>> dis(n, vector<int>(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 = 0, r = (int)1e9;
	while (l <= r) {
		int md = (l + r) >> 1;

		vector<vector<int>> d(n, vector<int>(n, (ll)1e18));
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++)
				d[i][j] = md * ((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: 0 / 12
• Subtask 2: 0 / 21
• Subtask 3: 0 / 33
• Subtask 4: 0 / 34