Submission #163433

#	Time	Username	Problem	Language	Result	Execution time	Memory
163433		KonaeAkira	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	141 ms	2232 KiB

merchant

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>

const int MAX_N = 1e2 + 5;
const int MAX_K = 1e3 + 5;

int n, m, k, buy[MAX_K], sell[MAX_N], prof[MAX_N][MAX_N], dist[MAX_N][MAX_N];
long long last_prof[MAX_N], last_dist[MAX_N], ans;

struct data { int ind; long long prof, dist; };
bool operator < (const data &lhs, const data &rhs) { return lhs.dist > rhs.dist; }

void solve(int s)
{
	memset(last_prof, 0xff, sizeof(last_prof));
	memset(last_dist, 0x00, sizeof(last_dist));
	std::priority_queue<data> q;
	for (int i = 1; i <= n; ++i)
		q.push({i, prof[s][i], dist[s][i]});
	while (!q.empty())
	{
		data cur = q.top(); q.pop();
		//printf("%d %lld %lld\n", cur.ind, cur.prof, cur.dist);
		if (last_prof[cur.ind] * cur.dist < cur.prof * last_dist[cur.ind])
		{
			last_prof[cur.ind] = cur.prof;
			last_dist[cur.ind] = cur.dist;
			ans = std::max(ans, (cur.prof + prof[cur.ind][s]) / (cur.dist + dist[cur.ind][s]));
			//printf("ans %lld\n", ans);
			for (int i = 1; i <= n; ++i)
				if (last_prof[i] * dist[cur.ind][i] < prof[cur.ind][i] * last_dist[i])
					q.push({i, cur.prof + prof[cur.ind][i], cur.dist + dist[cur.ind][i]});
		}
	}
}

int main()
{
	memset(dist, 0x3f, sizeof(dist));
	memset(buy, 0x7f, sizeof(buy));
	memset(sell, 0x7f, sizeof(sell));
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= n; ++i)
		for (int j = 0; j < k; ++j)
		{
			int b, s; scanf("%d%d", &b, &s);
			if (b != -1) { buy[i] = b; sell[i] = s; }
		}
	for (int i = 0; i < m; ++i)
	{
		int u, v, d; scanf("%d%d%d", &u, &v, &d);
		dist[u][v] = d;
	}
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			for (int k = 1; k <= n; ++k)
				dist[j][k] = std::min(dist[j][k], dist[j][i] + dist[i][k]);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			for (int p = 0; p < k; ++p)
				prof[i][j] = std::max(prof[i][j], sell[j] - buy[i]);
	for (int i = 1; i <= n; ++i)
		solve(i);
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:44: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:48:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int b, s; scanf("%d%d", &b, &s);
              ~~~~~^~~~~~~~~~~~~~~~
merchant.cpp:53:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v, d; scanf("%d%d%d", &u, &v, &d);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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