Submission #1260083

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260083		Seyyed_Mojtaba_Mortazavi	Travelling Merchant (APIO17_merchant)	C++20	12 / 100	34 ms	2368 KiB

merchant

#include <bits/stdc++.h>

using namespace std;

#define int long long int

const int INF = 1e18 + 10;
const int MAXN = 1e3 + 10;

int B[MAXN][MAXN];
int S[MAXN][MAXN];
int dist[MAXN][MAXN];

signed main()
{
	int n, m, k, ans = 0;
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			dist[i][j] = INF;
		}
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= k; j++)
		{
			cin >> B[i][j] >> S[i][j];
		}
	}
	for (int i = 1; i <= m; i++)
	{
		int v, u, w;
		cin >> v >> u >> w;
		dist[v][u] = min(dist[v][u], w);
	}
	for (int k = 1; k <= n; k++)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}
	for (int i = 1; i <= k; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (B[1][i] == -1 || S[j][i] == -1 || dist[1][j] == INF || dist[j][1] == INF)
				continue;
			int t = dist[1][j] + dist[j][1];
			int val = S[j][i] - B[1][i];
			ans = max(ans, val / t);
		}
	}
	cout << ans << endl;
	return 0;
}

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