Submission #690980

#	Time	Username	Problem	Language	Result	Execution time	Memory
690980		amir	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	29 ms	5708 KiB

merchant

/*
<< in the name of Allah >>
*/

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll ;
typedef pair<int , int> pii ;
typedef pair<ll , ll> pll ;
#define ps push_back
#define pb pop_back
#define mp make_pair
#define all(x) x.begin() , x.end() 
#define sz(x) (int)x.size() 
#define debug(a) cout<<"debug: "<<(#a)<<" = "<<a<<'\n'
#define debugAr(a) cout << "Array " << (#a) << " :\n" ;for (int TMP : a) cout << TMP << " " ; cout << '\n' 
#define f first
#define s second


const ll maxn = 1e3+5 , maxk = 1e3 + 4 , inf = 1e12 , MX = 1e18 ;
ll n , m , k ;
ll S[maxn][maxk] , B[maxn][maxk] ;
vector<pll > adj[maxn] ;
ll d[maxn][maxn] , f[maxn][maxn] , c[maxn][maxn] , td[maxn][maxn] ;


bool check(ll x){
	for (int i = 0 ; i < n ; i++){
		for (int j = 0 ;j < n ; j++){
			if (x > (MX/d[i][j])){
				f[i][j] = inf ;
			}
			else{
				f[i][j] = x*d[i][j]-c[i][j] ;
			}
			td[i][j] = f[i][j] ;
		}
		td[i][i] = 0 ;
	}
	
	for (int cnt = 0 ; cnt < n ; cnt++){
		for (int i = 0 ; i < n; i++){
			for (int j = 0 ; j < n ; j++){
				td[i][j] = min(td[i][j] , (td[i][cnt] + td[cnt][j])) ;
			}
		}
	}
	
	for (int i = 0 ;i < n ; i++){
		for (int j = 0 ; j < n ; j++){
			if (j == i) continue ;
			if ((td[i][j]+td[j][i]) <= 0){
				return 1 ;
			}
		}
	}
	
	return 0 ;
	
}

int main()
{
    ios::sync_with_stdio(false) ; 
	cin.tie(NULL) ;
	cout.tie(NULL) ;
	
	cin >> n >> m >> k ;
	
	for (int i = 0 ; i < n ; i++){
		for (int j = 0 ; j < k ;j++){
			cin >> B[i][j] >> S[i][j] ;
			if (B[i][j] == -1) B[i][j] = inf ;
			if (S[i][j] == -1) S[i][j] = 0-inf ;
		}
	}
	
	for (int i = 0 ; i < m ; i++){
		ll u , v , t ;
		cin >> u >> v >> t ; u-- , v-- ;
		
		adj[u].ps(mp(v , t)) ;
		d[u][v] = t ;
	}
	for (int i = 0 ; i < n; i++){
		for (int j = 0 ; j < n ; j++){
			if (d[i][j]) continue ;
			d[i][j] = inf ;	
		}
		d[i][i] = 0 ;
	}
	
	for (int cnt = 0 ; cnt < n ; cnt++){
		for (int i = 0 ; i < n; i++){
			for (int j = 0 ; j < n ; j++){
				if (d[i][cnt] != inf && d[cnt][j] != inf)
					d[i][j] = min(d[i][j] , (d[i][cnt] + d[cnt][j])) ;
			}
		}
	}
	
	for (int i = 0 ; i < n ; i++){
		for (int j = 0 ; j < n ; j++){
			if (d[i][j] == inf){
				c[i][j] = 0-inf ;
				continue ;
			}
			c[i][j] = 0 ;
			
			for (int h = 0 ; h < k ; h++){
				//if (S[j][h] == -1 || B[i][h] == -1) continue ;
				c[i][j] = max(c[i][j] , (S[j][h]-B[i][h])) ;
			}
			
		}
	}
	
	if (!check(1)){
		cout << 0 << '\n' ;
		return 0 ;
	}
	
	ll l = 1 , r = 1e11 ;
	
	while (l < r-1){
		ll mid = (l+r) / 2 ;
		if (check(mid)){
			l = mid ;
		}
		else {
			r = mid ;
		}
	}
	
	cout << l << '\n' ;
}

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