Submission #454784

#	Time	Username	Problem	Language	Result	Execution time	Memory
454784		sean617	Travelling Merchant (APIO17_merchant)	C++98	100 / 100	122 ms	2468 KiB

merchant

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

typedef long long ll;
ll n, m, k, tc, l, r, md, ans, M = 1e9, mx, B[N][1005], S[N][1005], di[N][N], d[N][N];
struct str {
	ll z, c1, c2;
};

bool operator < (str p, str q) {
	return p.c1 * q.c2 < q.c1 * p.c2;
}
vector<str> a, b;
int main()
{
	ll i, j, t1, t2, t3, kk, us, ut;
	str t;
	cin >> n >> m >> k;
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= k; j++) {
			scanf ("%lld %lld", &B[i][j], &S[i][j]);
		}
	}
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= n; j++) {
			di[i][j] = M;
		}
	}
	for (i = 0; i < m; i++) {
		scanf ("%lld %lld %lld", &t1, &t2, &t3);
		di[t1][t2] = min(di[t1][t2], t3);
	}
	for (kk = 1; kk <= n; kk++) {
		for (i = 1; i <= n; i++) {
			for (j = 1; j <= n; j++) {
				di[i][j] = min(di[i][j], di[i][kk] +di[kk][j]);
			}
		}
	}
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= n; j++) {
//			if (i == j) continue;
//			if (di[i][j] == M) {a.push_back({i, j, -M}); continue;}
			mx = -1;
			for (kk = 1; kk <= k; kk++) {
				if (B[i][kk] != -1 && S[j][kk] != -1 && S[j][kk] - B[i][kk] > 0) mx = max(mx, S[j][kk] - B[i][kk]);
			}
			a.push_back({i, j, (mx == -1 ? 0 : mx)});
		}
	}
	ans = 0;
	l = 1;
	r = 1e9;
	bool up;
	while (l < r) {
		md = (l + r) / 2;
		b.clear();
		for (i = 0; i < a.size(); i++) {
			t1 = a[i].z;
			t2 = a[i].c1;
			t3 = md * di[t1][t2] - a[i].c2;
			d[t1][t2] = t3;
//			b.push_back({t1, t2, t3});
//			if (t3 > 0)
		}
//		for (i =1; i <= n; i++) d[i][i] = 0;
//		for (i = 1; i <= n; i++) d[i] = M;
//		d[1] = 0;
//		for (i = 0; i <= n; i++) {
//			up = 0;
//			for (j = 0; j < b.size(); j++) {
//				t1 = b[j].z;
//				t2 = b[j].c1;
//				if (d[t1] + b[j].c2 < d[t2]) {d[t2] = d[t1] + b[j].c2; up = 1;}
//			}
//			if (!up) break;
//		}
		for (kk =1; kk <= n; kk++) {
			for (i = 1; i <= n; i++) {
				for (j = 1; j <= n; j++) d[i][j] = min(d[i][j], d[i][kk] + d[kk][j]);
			}
		}
		for (i = 1; i <= n; i++) if (d[i][i] <= 0) break;
		if (i <= n) {l = md +1; ans = md;}
		else r = md;
	}
	cout << ans;
//	mx = 0;
//	for (tc = 1; tc <= n; tc++) {
//		for (i = 1; i <= n; i++) {dt[i] = -1; ds[i] = -1;}
//		dt[tc] = 0; ds[tc] = 0;
//		while ()
//		for (j = 0; j <= n; j++) {
//			for (i = 0; i < a.size(); i++) {
//				t1 = a[i].z;
//				t2 = a[i].c1;
//				if (dt[t1] == -1) continue;
//				ut = dt[t1] + di[t1][t2];
//				us = ds[t1] + a[i].c2;
//				if (t2 == tc) mx = max(mx, us / ut);
//				else {
//					if (dt[t2] == -1 || us * dt[t2] > ut * ds[t2]) {ds[t2] = us; dt[t2] = ut;}
//				}
//			}
//		}
//	}
//	cout << mx << endl;
    return 0;
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:61:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<str>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   for (i = 0; i < a.size(); i++) {
      |               ~~^~~~~~~~~~
merchant.cpp:19:27: warning: unused variable 'us' [-Wunused-variable]
   19 |  ll i, j, t1, t2, t3, kk, us, ut;
      |                           ^~
merchant.cpp:19:31: warning: unused variable 'ut' [-Wunused-variable]
   19 |  ll i, j, t1, t2, t3, kk, us, ut;
      |                               ^~
merchant.cpp:20:6: warning: unused variable 't' [-Wunused-variable]
   20 |  str t;
      |      ^
merchant.cpp:57:7: warning: unused variable 'up' [-Wunused-variable]
   57 |  bool up;
      |       ^~
merchant.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |    scanf ("%lld %lld", &B[i][j], &S[i][j]);
      |    ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:33:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   scanf ("%lld %lld %lld", &t1, &t2, &t3);
      |   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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