Submission #308273

#	Time	Username	Problem	Language	Result	Execution time	Memory
308273		shivensinha4	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	117 ms	8312 KiB

merchant

#include <bits/stdc++.h> 
using namespace std; 
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'

const int MXN = 100;
const ll INF = 1e15;

ll dist[MXN+1][MXN+1], gain[MXN+1][MXN+1], aux[MXN+1][MXN+1];

int main() {
	#ifdef shiven
	freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, m, k; cin >> n >> m >> k;
	vector<vector<vector<ll>>> cost(n, vector<vector<ll>>(k, vector<ll>(2)));
	
	for_(i, 0, n) for_(j, 0, k) cin >> cost[i][j][0] >> cost[i][j][1];
	for_(i, 0, n) for_(j, 0, n) dist[i][j] = INF;
	for_(i, 0, m) {
		int a, b; ll w; cin >> a >> b >> w;
		a -= 1; b -= 1;
		dist[a][b] = min(dist[a][b], w);
	}
	
	for_(p, 0, n) for_(i, 0, n) for_(j, 0, n) dist[i][j] = min(dist[i][j], dist[i][p]+dist[p][j]);
	
	for_(i, 0, n) for_(j, 0, n) {
		for_(p, 0, k) if (cost[i][p][0] != -1 and cost[j][p][1] != -1) gain[i][j] = max(gain[i][j], cost[j][p][1]-cost[i][p][0]);
	}
	
	ll lo = 0, hi = 1e9+1, ans = 0;
	while (lo < hi) {
		ll mid = (lo+hi) / 2;
		for_(i, 0, n) for_(j, 0, n) {
			if (dist[i][j] != INF) aux[i][j] = mid * dist[i][j] - gain[i][j];
			else aux[i][j] = INF;
		}
		
		bool valid = false;
		for_(p, 0, n) for_(i, 0, n) for_(j, 0, n) aux[i][j] = min(aux[i][j], aux[i][p]+aux[p][j]);
		for_(i, 0, n) if (aux[i][i] <= 0) {
			valid = true;
			break;
		}
		
		//cout << mid << " " << valid << endl;
		if (valid) {
			lo = mid+1; ans = mid;
		} else hi = mid;
	}
	
	cout << ans << endl;
	

	return 0;
}

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