Submission #258046

#	Time	Username	Problem	Language	Result	Execution time	Memory
258046		mohammad	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	104 ms	4216 KiB

merchant

#include<bits/stdc++.h>
using namespace std;
 
#define endl "\n"
#define OR |
typedef long long ll ;
const ll ooo = 1e14 ;
const ll oo = 2e9 ;
const double PI = acos(-1) ;
const ll M = 1e9 + 7  ;
const int N = 10000010  ;

ll b[101][1010] , s[101][1010] , d[101][101] , pro[101][101];
ll ans[101][101];
int n , m , k ;

bool cn(ll md){
	for(int i = 1 ; i <= n ; ++i) 
		for(int j = 1 ; j <= n ; ++j) ans[i][j] = md * d[i][j] - pro[i][j] ;
	for(int x = 1 ; x <= n ; ++x)
		for(int i = 1 ; i <= n ; ++i)
			for(int j = 1 ; j <= n ; ++j){
				ans[i][j] = min(ans[i][j] , ans[i][x] + ans[x][j]);
			}
	for(int i = 1 ; i <= n; ++i) 
		if(ans[i][i] <= 0) return 1;
	return 0 ;
}

int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	// #ifndef ONLINE_JUDGE
	// 	freopen("input" , "r" , stdin );
	// 	freopen("output" , "w" , stdout );
	// #endif
	cin >> n >> m >> k;
	for(int i = 1 ; i <= n ; ++i)
		for(int j = 0 ; j < k ; ++j){
			cin >> b[i][j] >> s[i][j];
		}
	for(int i = 1;  i <= n; ++i)
		for(int j = 1;  j <= n; ++j) d[i][j] = oo;
	for(int i = 0 ; i < m ; ++i){
		int x , y , z;
		cin >> x >> y >> z;
		d[x][y] = z;
	}
	for(int x = 1 ; x <= n ; ++x)
		for(int i = 1 ; i <= n ; ++i)
			for(int j = 1 ; j <= n ; ++j){
				d[i][j] = min(d[i][j] , d[i][x] + d[x][j]);
			}
	for(int i = 1 ; i <= n ; ++i)
		for(int j = 1 ; j <= n ; ++j){
			if(i != j && d[i][j] != oo)
				for(int x = 0 ; x < k ; ++x){
					if(b[i][x] > 0 && s[j][x] > 0) pro[i][j] = max(pro[i][j] , s[j][x] - b[i][x]);
				}
		}
	ll lo = 0 , hi = oo , best = 0;
	while(lo <= hi){
		ll md = (lo + hi) / 2;
		if(cn(md)) lo = md + 1 , best = md ;
		else hi = md - 1;
	}
	cout << best << endl;
}

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