Submission #276943

#	Time	Username	Problem	Language	Result	Execution time	Memory
276943		luciocf	여행하는 상인 (APIO17_merchant)	C++14	0 / 100	27 ms	2432 KiB

merchant

#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

const int maxn = 110;
const int maxk = 1e3+10;
const ll inf = 1e18+10;

bool menor(pii a, pii b)
{
	return a.ff*b.ss < b.ff*a.ss;
}

ll dist[maxn][maxn];

int b[maxn][maxk], s[maxn][maxk];

int main(void)
{
	int n, m, k;
	scanf("%d %d %d", &n, &m, &k);

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= k; j++)
			scanf("%d %d", &b[i][j], &s[i][j]);

	for (int i = 1; i <= n; i++)
		for (int j = i+1; j <= n; j++)
			dist[i][j] = dist[j][i] = inf;

	for (int i = 1; i <= m; i++)
	{
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w);

		dist[u][v] = min(dist[u][v], 1ll*w);
	}

	for (int l = 1; l <= n; l++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				dist[i][j] = min(dist[i][j], dist[i][l]+dist[l][j]);

	pii ans = {0, 1};

	for (int i = 2; i <= n; i++)
	{	
		if (dist[1][i] == inf || dist[i][1] == inf) continue;

		int q = dist[1][i]+dist[i][1];
		int p = 0;

		for (int j = 1; j <= k; j++)
			if (b[1][j] && s[i][j])
				p = max(p, s[i][j]-b[1][j]);

		pii aux = {p/__gcd(p, q), q/__gcd(p, q)};

		if (menor(aux, ans)) ans = aux;
	}

	printf("%lld\n", ans.ff/ans.ss);
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |  scanf("%d %d %d", &n, &m, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:31:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   31 |    scanf("%d %d", &b[i][j], &s[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |   scanf("%d %d %d", &u, &v, &w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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