제출 #543279

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
543279		amunduzbaev	여행하는 상인 (APIO17_merchant)	C++17	100 / 100	87 ms	4112 KiB

merchant

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
#define int long long
const long long inf = 1e18;
const int N = 105;
int d[N][N], s[N][N];
int tr[N][1005][2];
int t[N][N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m, k; cin>>n>>m>>k;
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) d[i][j] = inf;
	for(int i=1;i<=n;i++){
		for(int j=0;j<k;j++){
			cin>>tr[i][j][0]>>tr[i][j][1];
		}
	}
	
	for(int i=0;i<m;i++){
		int a, b, c; cin>>a>>b>>c;
		d[a][b] = min(d[a][b], c);
	}
	
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int l=0;l<k;l++){
				if(~tr[i][l][0] && ~tr[j][l][1]){
					s[i][j] = max(s[i][j], tr[j][l][1] - tr[i][l][0]);
				}
			}
		}
	}
	
	auto check = [&](int f){
		for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) t[i][j] = -inf;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(i == j || d[i][j] == inf) continue;
				t[i][j] = max(t[i][j], s[i][j] - d[i][j] * f);
			}
		}
		for(int k=1;k<=n;k++){
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					t[i][j] = max(t[i][j], t[i][k] + t[k][j]);
				}
			}
		}
		
		//~ for(int i=1;i<=n;i++){
			//~ for(int j=1;j<=n;j++){
				//~ cout<<t[i][j]<<" ";
			//~ } cout<<"\n";
		//~ } cout<<"\n";
		
		for(int i=1;i<=n;i++){
			if(t[i][i] >= 0) return true;
		} return false;
	};
	
	int l = 0, r = 1e9;
	while(l < r){
		int m = (l + r + 1) >> 1;
		if(check(m)) l = m;
		else r = m - 1;
	}
	
	cout<<l<<"\n";
}

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