Submission #379960

#	Time	Username	Problem	Language	Result	Execution time	Memory
379960		rainboy	Travelling Merchant (APIO17_merchant)	C11	100 / 100	97 ms	3436 KiB

merchant

#include <stdio.h>
#include <string.h>

#define N	100
#define C	1000

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

long long cc[N][N]; int n;

int bellman_ford() {
	static long long dd[N], dd_[N];
	static int kk[N], kk_[N];
	int r, i, j;

	memset(dd, 0, n * sizeof *dd), memset(kk, 0, n * sizeof *kk);
	for (r = 0; r < n; r++) {
		int upd;

		memcpy(dd_, dd, n * sizeof *dd), memcpy(kk_, kk, n * sizeof *kk);
		upd = 0;
		for (i = 0; i < n; i++)
			for (j = 0; j < n; j++)
				if (i != j) {
					long long d = dd[i] + cc[i][j];
					int k = kk[i] + 1;

					if (dd_[j] > d || dd_[j] == d && kk_[j] < k)
						dd_[j] = d, kk_[j] = k, upd = 1;
				}
		memcpy(dd, dd_, n * sizeof *dd_), memcpy(kk, kk_, n * sizeof *kk_);
		if (!upd)
			return 0;
	}
	return 1;
}

int main() {
	static int bb[N][C], ss[N][C], dd[N][N], pp[N][N];
	int m, c, h, i, j, k, lower, upper;

	scanf("%d%d%d", &n, &m, &c);
	for (i = 0; i < n; i++)
		for (h = 0; h < c; h++)
			scanf("%d%d", &bb[i][h], &ss[i][h]);
	for (i = 0; i < n; i++) {
		memset(dd[i], 0x3f, n * sizeof *dd[i]);
		dd[i][i] = 0;
	}
	while (m--) {
		int d;

		scanf("%d%d%d", &i, &j, &d), i--, j--;
		dd[i][j] = d;
	}
	for (k = 0; k < n; k++)
		for (i = 0; i < n; i++)
			for (j = 0; j < n; j++)
				dd[i][j] = min(dd[i][j], dd[i][k] + dd[k][j]);
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			for (h = 0; h < c; h++)
				if (bb[i][h] != -1 && ss[j][h] != -1)
					pp[i][j] = max(pp[i][j], ss[j][h] - bb[i][h]);
	lower = 0, upper = 1000000001;
	while (upper - lower > 1) {
		int c = (lower + upper) / 2;

		for (i = 0; i < n; i++)
			for (j = 0; j < n; j++)
				cc[i][j] = (long long) dd[i][j] * c - pp[i][j];
		if (bellman_ford())
			lower = c;
		else
			upper = c;
	}
	printf("%d\n", lower);
	return 0;
}

Compilation message (stderr)

merchant.c: In function 'bellman_ford':
merchant.c:29:36: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   29 |      if (dd_[j] > d || dd_[j] == d && kk_[j] < k)
      |                        ~~~~~~~~~~~~^~~~~~~~~~~~~
merchant.c: In function 'main':
merchant.c:43:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   43 |  scanf("%d%d%d", &n, &m, &c);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.c:46:4: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   46 |    scanf("%d%d", &bb[i][h], &ss[i][h]);
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.c:54:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   54 |   scanf("%d%d%d", &i, &j, &d), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~

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