Submission #497138

#	Time	Username	Problem	Language	Result	Execution time	Memory
497138		Sohsoh84	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	188 ms	3992 KiB

merchant

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;

const ll MAXN = 100 + 10;
const ll MAXK = 1000 + 10;
const ll INF = 1e18; // ?

ll n, m, k, B[MAXN][MAXK], S[MAXN][MAXK], dist[MAXN][MAXN], max_prof[MAXN][MAXN], tdist[MAXN][MAXN];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	for (int i = 0; i < MAXN; i++) {
		fill(dist[i], dist[i] + MAXN, INF);
		dist[i][i] = 0;
	}

	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= k; j++) cin >> B[i][j] >> S[i][j];

	for (int i = 1; i <= m; i++) {
		int u, v, d;
		cin >> u >> v >> d;
		dist[u][v] = min(dist[u][v], 1ll * d);
	}

	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int t = 1; t <= k; t++)
				if (S[j][t] >= 0 && B[i][t] >= 0)
					max_prof[i][j] = max(max_prof[i][j], S[j][t] - B[i][t]);
			if (dist[i][j] == INF) max_prof[i][j] = 0;
		}
	}
	

	ll l = 0, r = ll(1e9) + 10;
	while (l < r) {
		ll mid = (l + r + 1) >> 1;	
		
		bool flag = false;
		memset(tdist, 63, sizeof tdist); //

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (dist[i][j] <= (tdist[i][j] - max_prof[i][j]) / mid) //
					tdist[i][j] = min(tdist[i][j], dist[i][j] * mid - max_prof[i][j]); //
				
			//	cerr << tdist[i][j] << sep;
			}

			//cerr << endl;
	
			tdist[i][i] = 1;
		}	

		for (int k = 1; k <= n; k++)
			for (int v = 1; v <= n; v++)
				for (int u = 1; u <= m; u++)
					tdist[v][u] = min(tdist[v][u], tdist[v][k] + tdist[k][u]);

		// loops
		for (int v = 1; v <= n; v++)
			flag |= (tdist[v][v] <= 0);

		if (flag) l = mid;
		else r = mid - 1;
	}

	cout << l << endl;
	return 0;
}

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