Submission #111457

#	Time	Username	Problem	Language	Result	Execution time	Memory
111457		diamond_duke	Travelling Merchant (APIO17_merchant)	C++11	100 / 100	103 ms	3448 KiB

merchant

#include <algorithm>
#include <cstring>
#include <cstdio>
using ll = long long;
inline void floyd(ll dis[][105], int n)
{
	for (int k = 0; k < n; k++)
	{
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
				dis[i][j] = std::min(dis[i][j], dis[i][k] + dis[k][j]);
		}
	}
}
int buy[105][1005], sell[105][1005], profit[105][105];
ll dis[105][105], cost[105][105];
int main()
{
	// freopen("APIO2017-T3.in", "r", stdin);
	int n, m, k;
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < k; j++)
			scanf("%d%d", buy[i] + j, sell[i] + j);
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			for (int x = 0; x < k; x++)
			{
				if (~buy[i][x] && ~sell[j][x])
					profit[i][j] = std::max(profit[i][j], sell[j][x] - buy[i][x]);
			}
		}
	}
	memset(dis, 0x3f, sizeof(dis));
	for (int i = 0; i < m; i++)
	{
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		dis[--u][--v] = w;
	}
	floyd(dis, n);
	int l = 0, r = 1e9, res = -1;
	while (l <= r)
	{
		int mid = l + r >> 1;
		memset(cost, 0x3f, sizeof(cost));
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (dis[i][j] < 1e18)
					cost[i][j] = (ll)dis[i][j] * mid - profit[i][j];
			}
		}
		floyd(cost, n);
		bool flg = false;
		for (int i = 0; i < n; i++)
			flg |= cost[i][i] <= 0;
		if (flg)
		{
			res = mid;
			l = mid + 1;
		}
		else
			r = mid - 1;
	}
	printf("%d\n", res);
	return 0;
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:50:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + r >> 1;
             ~~^~~
merchant.cpp:22: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:26:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", buy[i] + j, sell[i] + j);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &u, &v, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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