제출 #690954

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
690954		amir	여행하는 상인 (APIO17_merchant)	C++14	0 / 100	63 ms	3408 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 = 105 , maxk = 1e3 + 4 , inf = 1e13 ;
int n , m , k ;
ll S[maxn][maxk] , B[maxn][maxk] ;
vector<pii > adj[maxn] ;
ll d[maxn][maxn] , f[maxn][maxn] , c[maxn][maxn] , td[maxn] ;


bool check(ll x){
	for (int i = 0 ; i < n ; i++){
		for (int j = 0 ;j < n ; j++){
			f[i][j] = x*d[i][j]-c[i][j] ;
		}
		
	}
	for (int i = 0 ; i < n ; i++){
		td[i] = inf ;
	}
	
	td[0] = 0 ;
	
	for (int cnt = 0 ;cnt < n; cnt++){
		for (int i = 0 ;i < n ; i++){
			for (int j = 0 ;j < n ; j++){
				if (i == j || d[i][j] == inf) continue ;
				if (td[i] < inf){
					td[j] = min(td[j] , td[i]+f[i][j]) ;
				}
			}
		}
	}
	
	
	for (int i = 0 ;i < n ; i++){
		for (int j = 0 ;j < n ; j++){
			if (i == j) continue ;
			if (td[i] < inf){
				if (td[j] > (td[i]+f[i][j])){
					return true ;
				}
			}
		}
	}
	
	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] ;
		}
	}
	
	for (int i = 0 ; i < m ; i++){
		int 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++){
				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])) ;
			}
			
		}
	}
	
	
	//cout << check(2) ;
	
	
	ll l = 0 , r = 1e10 ;
	
	while (l < r-1){
		ll mid = (l+r) / 2 ;
		if (check(mid-1)){
			l = mid ;
		}
		else {
			r = mid ;
		}
	}
	
	cout << l << '\n' ;
}

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