Submission #211171

#	Time	Username	Problem	Language	Result	Execution time	Memory
211171		spdskatr	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	159 ms	3448 KiB

merchant

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>

using namespace std;

int N, M, K, b[105][1005], s[105][1005];
long long adj[105][105], profit[105][105];
long long tot[105][105];

int solve(int offset) {
	for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) {
		tot[i][j] = profit[i][j] - offset * adj[i][j];
	}
	for (int m = 1; m <= N; m++) for (int u = 1; u <= N; u++) for (int v = 1; v <= N; v++) {
		if (tot[u][m] + tot[m][v] < 0 && tot[u][m] >= 0 && tot[m][v] >= 0) return 1;
		tot[u][v] = max(tot[u][v], tot[u][m] + tot[m][v]);
	}
	for (int u = 1; u <= N; u++) for (int v = 1; v <= N; v++) {
		if (u != v && tot[u][v] + tot[v][u] >= 0) {
			return 1;
		}
	}
	return 0;
}

int main() {
	scanf("%d %d %d", &N, &M, &K);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= K; j++) {
			scanf("%d %d", &b[i][j], &s[i][j]);
		}
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			adj[i][j] = 2000000005;
		}
		adj[i][i] = 0;
	}
	for (int i = 0; i < M; i++) {
		int v, w, t;
		scanf("%d %d %d", &v, &w, &t);
		adj[v][w] = t;
	}
	for (int m = 1; m <= N; m++) for (int u = 1; u <= N; u++) for (int v = 1; v <= N; v++) {
		adj[u][v] = min(adj[u][v], adj[u][m] + adj[m][v]);
	}
	for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) for (int k = 1; k <= K; k++) {
		if (s[j][k] != -1 && b[i][k] != -1)
			profit[i][j] = max(profit[i][j], (long long)s[j][k] - b[i][k]);
	}
	int lo = 0, hi = 1000000001;
	while (lo + 1 < hi) {
		int mid = (lo + hi) / 2;
		if (solve(mid)) lo = mid;
		else hi = mid;
	}
	printf("%d\n", lo);
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &N, &M, &K);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:32:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &b[i][j], &s[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &v, &w, &t);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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