제출 #258041

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
258041		mohammad	여행하는 상인 (APIO17_merchant)	C++14	0 / 100	23 ms	3328 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 = 2 ; i <= n ; ++i)
		for(int j = 0 ; j < k ; ++j){
			if(b[1][j] > 0 && s[i][j] > 0) pro[1][i] = max(pro[1][i] , s[i][j] - b[1][j]);
		}
	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