Submission #885021

#	Time	Username	Problem	Language	Result	Execution time	Memory
885021		Hakiers	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	87 ms	3964 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int MAXN = 1e2 + 7;
constexpr ll oo = 8e18;
ll dist[MAXN][MAXN];
ll profit[MAXN][MAXN];
ll cycle[MAXN][MAXN];
pair<ll, ll> market[MAXN][1007];
int n, m, k;

void computeDist(){
	for(int l = 1; l <= n; l++)
	for(int i = 1; i <= n; i++)
	for(int j = 1; j <= n; j++)
		if(dist[i][l] != oo && dist[l][j] != oo)
		dist[i][j] = min(dist[i][j], dist[i][l] + dist[l][j]);
}

void computeProfit(){
	for(int i = 1; i <= n; i++)
	for(int j = 1; j <= n; j++)
		profit[i][j] = -oo;

	for(int l = 1; l <= k; l++)
	for(int i = 1; i <= n; i++)
	for(int j = 1; j <= n; j++)
		if(market[i][l].first != -1 && market[j][l].second != -1 && dist[i][j] != oo) 
			profit[i][j] = max(profit[i][j], market[j][l].second - market[i][l].first);
}

void prepare(ll x){
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			if(dist[i][j] != oo)
			cycle[i][j] = (dist[i][j] * x) - profit[i][j];
}

bool check(ll x){
	prepare(x);
	
	for(int l = 1; l <= n; l++)
	for(int i = 1; i <= n; i++)
	for(int j = 1; j <= n; j++)
		cycle[i][j] = min(cycle[i][j], cycle[i][l] + cycle[l][j]);
	
	
	for(int l = 1; l <= n; l++)
	for(int i = 1; i <= n; i++)
	for(int j = 1; j <= n; j++)
		if(cycle[i][j] > cycle[i][l] + cycle[l][j]) return true;
	
	return false;
}

ll BS(){
	ll l = 0, r = 1e9, mid;
	
	while(l < r){
		mid = (l+r)/2;
		if(check(mid)) l = mid + 1;
		else r = mid;
	}
	
	if(check(l)) return l;
	
	return --l;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> k;
	
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= k; j++)
			cin >> market[i][j].first >> market[i][j].second;
	
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			if(i != j) dist[i][j] = oo;
			
	for(int i = 1; i <= m; i++){
		int u, v;
		ll t;
		cin >> u >> v >> t;
		dist[u][v] = min(dist[u][v], t);
	}
	
	computeDist();
	computeProfit();
	
	
	cout << BS() << "\n";

}

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