Submission #258043

#	Time	Username	Problem	Language	Result	Execution time	Memory
258043		mohammad	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	33 ms	2040 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 i = 1 ; i <= n ; ++i)
		for(int j = 1 ; j <= n ; ++j){
			ans[i][i] = min(ans[i][i] , ans[i][j] + ans[j][i]);
		}
	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 i = 1 ; i <= n ;++i)
		for(int j = 1 ; j <= n ;++j)
			for(int x = 1 ; x <= n ;++x){
				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)
			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: 0 / 12
• Subtask 2: 0 / 21
• Subtask 3: 0 / 33
• Subtask 4: 0 / 34