Submission #1260122

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260122		Seyyed_Mojtaba_Mortazavi	여행하는 상인 (APIO17_merchant)	C++20	100 / 100	80 ms	3776 KiB

merchant

#include <bits/stdc++.h>

using namespace std;

#define int long long int

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

struct Edge {

	int v, u, p, t;	

};

int B[MAXN][MAXN];
int S[MAXN][MAXN];
int P[MAXN][MAXN];
int dis[MAXN][MAXN];
int dist[MAXN][MAXN];
vector <Edge> edge;

bool check(int n, int mid)
{
	for (auto [v, u, p, t] : edge)
		dis[v][u] = (t == INF ? INF : mid * t) - p;
	for (int k = 1; k <= n; k++)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
			}
		}
	}
	for (int i = 1; i <= n; i++)
	{
		if (dis[i][i] <= 0)
			return true;
	}
	return false;
}

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] = w;
	}
	for (int t = 1; t <= n; t++)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				dist[i][j] = min(dist[i][j], dist[i][t] + dist[t][j]);
			}
		}
	}
	for (int i = 1; i <= k; i++)
	{
		for (int v = 1; v <= n; v++)
		{
			for (int u = 1; u <= n; u++)
			{
				if (B[v][i] == -1 || S[u][i] == -1)
					continue;
				P[v][u] = max(P[v][u], S[u][i] - B[v][i]);
			}
		}
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			edge.push_back({i, j, P[i][j], dist[i][j]});
		}
	}
	int l = 0, r = sqrt(INF);
	while (r - l > 1)
	{
		int mid = (l + r) >> 1;
		if (check(n, mid))
			l = mid;
		else
			r = mid;
	}
	cout << l << endl;
	return 0;
}

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