Submission #266825

#	Time	Username	Problem	Language	Result	Execution time	Memory
266825		hanagasumi	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	139 ms	4344 KiB

merchant

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <deque>
#include <map>
#include <set>
#include <complex>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <random>

#define ft first
#define sc second
#define pb push_back
#define len(v) (int)v.size()
#define int ll
#define all(v) v.begin(), v.end()

using namespace std;
typedef long long ll;
typedef long double ld;

int inf = 1e18 + 100;
int infs = 1e9 + 100;

int n, m, k;
vector<vector<int>> cst;
vector<vector<int>> s;
vector<vector<int>> b;
vector<vector<int>> dst;
vector<vector<int>> dst0;
vector<vector<int>> dp;


vector<vector<pair<int, int>>> g;

bool solve(int x) {
	vector<vector<int>> dstn(n, vector<int> (n, -inf));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if(dst[i][j] == inf)
				continue;
			dstn[i][j] = max(dstn[i][j], cst[i][j] - x * dst[i][j]);
		}
	}
	for (int md = 0; md < n; md++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if(dstn[i][md] == -inf || dstn[md][j] == -inf)
					continue;
				dstn[i][j] = max(dstn[i][j], dstn[i][md] + dstn[md][j]);
			}
		}
	}
	for (int i = 0; i < n; i++) {
		if(dstn[i][i] >= 0) 
			return 1;
	}
	return 0;
}


signed main() {
	#ifdef PC
		freopen("in.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);


	cin >> n >> m >> k;
	cst = vector<vector<int>> (n, vector<int> (n, 0));
	dst = vector<vector<int>> (n, vector<int> (n, inf));	
	dst0 = vector<vector<int>> (n, vector<int> (n, inf));
	s = vector<vector<int>> (n, vector<int> (k, 0));
	b = vector<vector<int>> (n, vector<int> (k, 0));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < k; j++) {
			cin >> b[i][j] >> s[i][j];
		}
	}

	for (int i = 0; i < m; i++) {
		int a, b, w;
		cin >> a >> b >> w;
		a--, b--;
		dst[a][b] = min(dst[a][b], w);
	}
	for (int md = 0; md < n; md++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if(dst[i][md] < inf && dst[md][j] < inf) 
					dst[i][j] = min(dst[i][j], dst[i][md] + dst[md][j]);
			}
		}
	}


	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			dst0[j][i] = dst[i][j];
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int z = 0; z < k; z++) {
				if(b[i][z] == -1 || s[j][z] == -1) 
					continue;
				cst[i][j] = max(cst[i][j], s[j][z] - b[i][z]);
			}
		}
	}

	int l = 0, r = infs;
	while(r - l > 1) {
		int mid = (l + r) / 2;
		if(solve(mid)) 
			l = mid;
		else
			r = mid;
	}
	cout << l << endl;
	return 0;
}

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