Submission #1117033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117033		pedroslrey	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	107 ms	3356 KiB

merchant

#include <bits/stdc++.h>

using namespace std;
using lli = long long;

int main() {
	int n, m, k;
	cin >> n >> m >> k;

	vector<vector<int>> bs(n, vector<int>(k)), ss(n, vector<int>(k));
	for (int i = 0; i < n; ++i) 
		for (int j = 0; j < k; ++j)
			cin >> bs[i][j] >> ss[i][j];

	vector<vector<lli>> dist(n, vector<lli>(n, 1e18));
	for (int i = 0; i < m; ++i) {
		int u, v, w;
		cin >> u >> v >> w;

		dist[u - 1][v - 1] = w;
	}

	for (int i = 0; i < n; ++i)
		dist[i][i] = 0;

	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			for (int z = 0; z < n; ++z)
				if (dist[j][z] > dist[j][i] + dist[i][z])
					dist[j][z] = dist[j][i] + dist[i][z];

	vector<vector<int>> profit(n, vector<int>(n));
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j) {
			for (int z = 0; z < k; ++z) if (ss[j][z] != -1 && bs[i][z] != -1)
				profit[i][j] = max(profit[i][j], ss[j][z] - bs[i][z]);

			// cerr << "PROFIT " << i << " " << j << " "<< profit[i][j] << "\n";
		}

	auto bellman = [&](lli x) {
		vector<lli> pot(n);

		// cerr << "-> " << x << "\n";

		for (int i = 0; i <= n + 1; ++i) {
			bool change = false;
			for (int u = 0; u < n; ++u)
				for (int v = 0; v < n; ++v) if (u != v && dist[u][v] != 1e18) {
					if (dist[u][v]*x - profit[u][v] >= 1e16) continue;
					lli c = (dist[u][v]*x - profit[u][v])*100 - 1;

					if (pot[v] > pot[u] + c) {
						pot[v] = pot[u] + c;
						// cerr << u << " " << v << " " << c << " CHANGE!\n";
						change = true;
					}
				}

			if (i == n + 1 && change) return false;

			if (!change) break;
		}

		// for (lli x: pot)
		// 	cerr << x << " ";
		// cerr << "\n";

		return true;
	};

	lli l = 0, r = 1e9;
	while (l < r) {
		int m = (l + r)/2;

		if (bellman(m)) r = m;
		else l = m + 1;
	}

	cout << max(l-1, 0LL) << "\n";
}

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