Submission #657218

#	Time	Username	Problem	Language	Result	Execution time	Memory
657218		amirhoseinfar1385	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	159 ms	4140 KiB

merchant

#include<bits/stdc++.h>
using namespace std;
const long long maxn=102,maxm=9905,maxk=1001;
long long inf=1e9+10;
long long dis[maxn][maxn],cm[maxn][maxn],b[maxn][maxk],s[maxn][maxk];
long long n,m,k;
void aval(){
	for(long long i=0;i<n;i++){
		for(long long j=0;j<n;j++){
			for(long long h=0;h<k;h++){
				if(b[i][h]==-1||s[j][h]==-1){
					continue;
				}
				cm[i][j]=max(cm[i][j],s[j][h]-b[i][h]);
			}
		}
	}
	for(long long h=0;h<n;h++){
		for(long long i=0;i<n;i++){
			for(long long j=0;j<n;j++){
				dis[i][j]=min(dis[i][j],dis[i][h]+dis[h][j]);
			}
		}
	}
}

bool check(long long mid){
	vector<vector<long long>>fake(maxn,vector<long long>(maxn));
	for(long long i=0;i<n;i++){
		for(long long j=0;j<n;j++){
			if(dis[i][j]>=inf){
				fake[i][j]=-inf;
			}
			else{
				fake[i][j]=cm[i][j]-mid*dis[i][j];
			}
		}
	}	
	for(long long h=0;h<n;h++){
		for(long long i=0;i<n;i++){
			for(long long j=0;j<n;j++){
              	if(fake[i][h]>=inf||fake[h][j]>=inf){
                  	continue;
                }
				fake[i][j]=max(fake[i][j],fake[i][h]+fake[h][j]);
			}
		}
	}
	for(long long i=0;i<n;i++){
       //      if(mid==2){
     //    	 cout<<fake[i][i]<<endl;
        //  }
		if(fake[i][i]>=0){
			return 1;
		}
	}
	return 0;
}

int main(){
	cin>>n>>m>>k;
	for(long long i=0;i<n;i++){
		for(long long j=0;j<k;j++){
			cin>>b[i][j]>>s[i][j];
		}
	}
	for(long long i=0;i<maxn;i++){
		for(long long j=0;j<maxn;j++){
			dis[i][j]=inf;
		}
	}
	for(long long i=0;i<m;i++){
		long long u,v,w;
		cin>>u>>v>>w;
     	 u--;
     	 v--;
		dis[u][v]=min(w,dis[u][v]);
	}
 // cout<<s[0][1]<<" "<<b[2][1]<<endl;
	aval();
 // cout<<dis[0][2]<<" "<<dis[2][0]<<" "<<cm[0][2]<<" "<<cm[2][0]<<endl;
	long long low=0,high=1e9+20,mid;
	while(high-low>1){
		mid=(high+low)>>1;
		if(check(mid)){
			low=mid;
		}
		else{
			high=mid;
		}
	}
	cout<<low<<endl;
}

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