Submission #57387

#	Time	Username	Problem	Language	Result	Execution time	Memory
57387		thiago4532	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	88 ms	1592 KiB

merchant

#include <bits/stdc++.h>

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

bool check(int64_t eff){
	memset(g, 0x3f, sizeof g);

	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(dist[i][j] < inf) 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(1e9)+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], int64_t(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