Submission #1281477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281477		Jawad_Akbar_JJ	Travelling Merchant (APIO17_merchant)	C++20	100 / 100	101 ms	2316 KiB

merchant

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;
#define int long long
const int N = 105, inf = 1e17;
int d[N][N], d2[N][N], b[N][N * 10], s[N][N * 10], prf[N][N];

signed main(){
	int n, m, K;
	cin>>n>>m>>K;

	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<=n;i++){
		for (int j=1;j<=n;j++){
			if (i == j)
				continue;
			d[i][j] = 1e17;
			for (int k=1;k<=K;k++)
				if (min(b[i][k], s[j][k]) != -1)
				prf[i][j] = max(prf[i][j], - b[i][k] + s[j][k]);
		}
	}

	for (int i=1, a, b, c;i<=m;i++){
		cin>>a>>b>>c;
		d[a][b] = c;
	}

	for (int k=1;k<=n;k++){
		for (int i=1;i<=n;i++)
			for (int j=1;j<=n;j++)
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
	}

	int l = 0, r = 1e9 + 7;
	while (l + 1 < r){
		int mid = (l + r) / 2;
		// mid = 3;
		for (int i=1;i<=n;i++){
			for (int j=1;j<=n;j++){
				if (i == j)
					d2[i][j] = -inf;
				else
					d2[i][j] = prf[i][j] - min(mid, inf / d[i][j] + 1) * d[i][j];
			}
		}

		for (int k=1;k<=n;k++){
			for (int i=1;i<=n;i++)
				for (int j=1;j<=n;j++)
					d2[i][j] = max(d2[i][j], d2[i][k] + d2[k][j]);
		}

		bool t = 0;
		for (int i=1;i<=n;i++)
			t |= d2[i][i] >= 0;
		
		if (t)
			l = mid;
		else
			r = mid;
	}
	cout<<l<<'\n';

}

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