Submission #885214

#	Time	Username	Problem	Language	Result	Execution time	Memory
885214		Hakiers	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	67 ms	4328 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 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 && i != j) 
			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];
			else cycle[i][j] = oo;
		}
	}
}

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++)
		if(dist[i][l] != oo && dist[l][j] != oo)
		cycle[i][j] = min(cycle[i][j], cycle[i][l] + cycle[l][j]);
		
	/*	
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			cout << "i: " << i << " j " << j << " cycle: " << cycle[i][j] << "\n";
	
	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)
			if(cycle[i][j] > cycle[i][l] + cycle[l][j]) return true;
	
	
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			if(dist[i][j] != oo && dist[j][i] != oo && i != j)
				if(cycle[i][j] + cycle[j][i] <= 0) return true;
	*/
	
	for(int i = 1; i <= n; i++)
		if(cycle[i][i] <= 0) 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 max(--l, (ll)0);
}

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++)
			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();
	/*
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			cout << "i " << i << " j " << j << " profit " << profit[i][j] << "\n";
	
	
	check(1);
	cout << "\n";
	check(2);
	cout << "\n";
	check(3);
	cout << "\n";
	check(4);
	cout << "\n";
	*/
	cout << BS() << "\n";

}

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