Submission #732370

#	Time	Username	Problem	Language	Result	Execution time	Memory
732370		SanguineChameleon	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	94 ms	3404 KiB

merchant

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

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

const int maxN = 1e2 + 20;
const int maxK = 1e3 + 20;
const int inf1 = 1e9 + 20;
const long long inf2 = 1e18L + 20;
int buy[maxN][maxK];
int sell[maxN][maxK];
int dist[maxN][maxN];
int prof[maxN][maxN];
long long cost[maxN][maxN];
long long dist2[maxN];
int flag[maxN];
int N, M, K;

bool dfs(int u) {
	flag[u] = 0;
	for (int v = 1; v <= N; v++) {
		if (v != u && dist2[u] + cost[u][v] == dist2[v]) {
			if (flag[v] == 0 || (flag[v] == -1 && dfs(v))) {
				return true;
			}
		}
	}
	flag[u] = 1;
	return false;
}

bool check() {
	for (int i = 1; i <= N; i++) {
		dist2[i] = 0;
	}
	for (int iter = 0; iter < N; iter++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (dist2[j] < dist2[i] + cost[i][j]) {
					if (iter == N - 1) {
						return true;
					}
					dist2[j] = dist2[i] + cost[i][j];
				}
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		flag[i] = -1;
	}
	for (int i = 1; i <= N; i++) {
		if (flag[i] == -1 && dfs(i)) {
			return true;
		}
	}
	return false;
}

void just_do_it() {
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (i == j) {
				dist[i][j] = 0;
			}
			else {
				dist[i][j] = inf1;
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= K; j++) {
			cin >> buy[i][j] >> sell[i][j];
		}
	}
	for (int i = 1; i <= M; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		dist[u][v] = min(dist[u][v], w);
	}
	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++) {
			prof[i][j] = 0;
			for (int k = 1; k <= K; k++) {
				if (buy[i][k] != -1 && sell[j][k] != -1) {
					prof[i][j] = max(prof[i][j], sell[j][k] - buy[i][k]);
				}
			}
		}
	}
	int res = 0;
	int lt = 1;
	int rt = inf1;
	while (lt <= rt) {
		int mt = (lt + rt) / 2;
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (dist[i][j] == inf1) {
					cost[i][j] = -inf2;
				}
				else {
					cost[i][j] = 1LL * prof[i][j] - 1LL * dist[i][j] * mt; 
				}
			}
		}
		if (check()) {
			res = mt;
			lt = mt + 1;
		}
		else {
			rt = mt - 1;
		}
	}
	cout << res;
}

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