Submission #1259860

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259860		MasterDebater	Travelling Merchant (APIO17_merchant)	C++20	100 / 100	56 ms	2184 KiB

merchant

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define F first
#define S second
const ll N=105,K=1010,INF=LLONG_MAX/2;
ll n,m,k,lo=1,hi=1e9,mid,ans,s[N][K],b[N][K],t[N][N],p[N][N],dp[N][N];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m>>k;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++)t[i][j]=INF;
		for(int j=0;j<k;j++)cin>>b[i][j]>>s[i][j];
	}
	for(int i=0;i<m;i++){
		ll ai,bi,ci;
		cin>>ai>>bi>>ci,ai--,bi--;
		t[ai][bi]=ci;
	}
	
	for(int x=0;x<n;x++)
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				t[i][j]=min(t[i][j],t[i][x]+t[x][j]);
	
	
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			for(int x=0;x<k;x++)
				if(s[j][x]!=-1 and b[i][x]!=-1)p[i][j]=max(p[i][j],s[j][x]-b[i][x]);
	
	
	while(lo<=hi){
		mid=(lo+hi)/2;
		bool ok=0;
		for(int i=0;i<n;i++)for(int j=0;j<n;j++)dp[i][j]=mid*min(t[i][j],INF/mid)-p[i][j];
		
		for(int x=0;x<n;x++)
			for(int i=0;i<n;i++)
				for(int j=0;j<n;j++)
					dp[i][j]=min(dp[i][j],dp[i][x]+dp[x][j]);
		
		for(int i=0;i<n;i++)if(dp[i][i]<=0)ok=1;
		if(ok)ans=mid,lo=mid+1;
		else hi=mid-1;
	}
	cout<<ans;
	return 0;
}

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