Submission #57384

#	Time	Username	Problem	Language	Result	Execution time	Memory
57384		thiago4532	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	140 ms	26456 KiB

merchant

#include <bits/stdc++.h>
#define int int64_t

using namespace std;
const int maxn = 1e3 + 10, inf = 0x3f3f3f3f3f3f3f3f;
int n, m, k, dist[maxn][maxn];
int b[maxn][maxn], s[maxn][maxn], e[maxn][maxn], g[maxn][maxn];

bool check(int eff){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			g[i][j] = eff*dist[i][j] - e[i][j];
		}
	}

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

	for(int i=1;i<=n;i++)
		if(g[i][i] <= 0) return true;

	return false;
}

int buscab(){
	int ini=1, fim=int(1e18)+1, meio;
	while(fim - ini > 1){
		meio = (ini+fim)>>1;
		if(check(meio))
			ini = meio;
		else
			fim = meio;
	}
	return ini;
}



int32_t main(){
	ios::sync_with_stdio(false), cin.tie(0);
	memset(dist, 0x3f, sizeof dist);
	memset(b, -1, sizeof b);
	memset(s, -1, sizeof s);

	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<=m;i++){
		int u, v, d;
		cin >> u >> v >> d;
		dist[u][v] = min(dist[u][v], d);
	}

	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]);
			}
		}
	}

	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int l=1;l<=k;l++){
				if(s[j][k] != -1 && b[i][k] != -1)
					e[i][j] = max(e[i][j], s[j][k] - b[i][k]);
			}
		}
	}

	cout << buscab() << "\n";
	return 0;
}

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