Submission #373661

#	Time	Username	Problem	Language	Result	Execution time	Memory
373661		t12345	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	107 ms	1464 KiB

merchant

#include <iostream>
#include <cstdio>
#define N 105
#define K 1005
using namespace std;

typedef long long ll;
int n, m, k, b[N][K], s[N][K], pr[N][N], dt[N][N];
ll rt[N][N];
int lo, hi=1e9, md, ans;

bool f(int p) {
	int i, j, x;
	for(i=1; i<=n; i++) for(j=1; j<=n; j++) {
		rt[i][j] = (ll)p * dt[i][j] - pr[i][j];
	}
	for(x=1; x<=n; x++) for(i=1; i<=n; i++) for(j=1; j<=n; j++) {
		rt[i][j] = min(rt[i][j], rt[i][x] + rt[x][j]);
	}
	for(i=1; i<=n; i++) if(rt[i][i]<=0) return 1;
	return 0;
}

int main() {
	int i, j, x, u, v;
	cin >> n >> m >> k;
	for(i=1; i<=n; i++) for(j=1; j<=k; j++) scanf("%d%d", &b[i][j], &s[i][j]);
	for(i=1; i<=n; i++) for(j=1; j<=n; j++) for(x=1; x<=k; x++) {
		if(b[i][x]!=-1 && s[j][x]!=-1)
			pr[i][j] = max(pr[i][j], s[j][x] - b[i][x]);
	}
	for(i=1; i<=n; i++) for(j=1; j<=n; j++) dt[i][j] = 1e9;
	while(m--) scanf("%d%d", &u, &v), scanf("%d", &dt[u][v]);
	for(x=1; x<=n; x++) for(i=1; i<=n; i++) for(j=1; j<=n; j++) {
		dt[i][j] = min(dt[i][j], dt[i][x] + dt[x][j]);
	}
	while(lo <= hi) {
		md = lo+hi >> 1;
		if(f(md)) ans = md, lo = md+1;
		else hi = md-1;
	}
	cout << ans;
	return 0;
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:38:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |   md = lo+hi >> 1;
      |        ~~^~~
merchant.cpp:27:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |  for(i=1; i<=n; i++) for(j=1; j<=k; j++) scanf("%d%d", &b[i][j], &s[i][j]);
      |                                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:33:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |  while(m--) scanf("%d%d", &u, &v), scanf("%d", &dt[u][v]);
      |             ~~~~~^~~~~~~~~~~~~~~~
merchant.cpp:33:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |  while(m--) scanf("%d%d", &u, &v), scanf("%d", &dt[u][v]);
      |                                    ~~~~~^~~~~~~~~~~~~~~~~

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