Submission #454565

#	Time	Username	Problem	Language	Result	Execution time	Memory
454565		sean617	Travelling Merchant (APIO17_merchant)	C++98	33 / 100	505 ms	4168 KiB

merchant

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

typedef long long ll;
ll n, m, k, tc, M = 1e16, mx, B[N][1005], S[N][1005], di[N][N], ds[N], dt[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;
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 (di[i][j] == M || i == j) 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)});
		}
	}
	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;
		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:58:18: 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]
   58 |    for (i = 0; i < a.size(); i++) {
      |                ~~^~~~~~~~~~
merchant.cpp:20:6: warning: unused variable 't' [-Wunused-variable]
   20 |  str t;
      |      ^
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: 0 / 33
• Subtask 4: 0 / 34