Submission #114309

#	Time	Username	Problem	Language	Result	Execution time	Memory
114309		Bruteforceman	Travelling Merchant (APIO17_merchant)	C++11	100 / 100	917 ms	3576 KiB

merchant

#include "bits/stdc++.h"
using namespace std;
int n, m, k;
int b[105][1005];
int s[105][1005];
long long a[105][105];
long long opt[105][105];
const long long inf = 2e9;

bool good(long long guess) {
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			opt[i][j] = inf;
		}
	}
	for(int item = 1; item <= k; item++) {
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				if(i == j) continue;
				opt[i][j] = min(opt[i][j], guess * a[i][j]);
				if(b[i][item] != -1 && s[j][item] != -1) {
					opt[i][j] = min(opt[i][j], b[i][item] - s[j][item] + guess * a[i][j]);
				}
			}
		}
	}
	for(int x = 1; x <= n; x++) {
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				opt[i][j] = min(opt[i][j], opt[i][x] + opt[x][j]);
			}
		}
	}
	for(int i = 1; i <= n; i++) {
		if(opt[i][i] <= 0) return true;
	}
	return false;
}

int search(int b, int e) {
	if(b == e) {
		return b;
	}
	int mid = (b + e + 1) >> 1;
	if(good(mid)) {
		return search(mid, e);
	} else {
		return search(b, mid - 1);
	}
}

int main(int argc, char const *argv[])
{
	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++) {
			a[i][j] = inf;
		}
		a[i][i] = 0;
	}
	for(int i = 1; i <= m; i++) {
		int p, q, r;
		scanf("%d %d %d", &p, &q, &r);
		a[p][q] = r;
	}
	for(int x = 1; x <= n; x++) {
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				a[i][j] = min(a[i][j], a[i][x] + a[x][j]);
			}
		}
	}
	printf("%d\n", search(0, 1000000000));
	return 0;
}

Compilation message (stderr)

merchant.cpp: In function 'int main(int, const char**)':
merchant.cpp:54: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:57: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:68:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &p, &q, &r);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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