Submission #163272

#	Time	Username	Problem	Language	Result	Execution time	Memory
163272		HungAnhGoldIBO2020	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	108 ms	4332 KiB

merchant

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=101;
const int K=1001;
const int inf=1e9+7;
int dis[N][N],b[N][K],s[N][K],max1[N][N],maxdis[N][N];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,i,j,k,l,num,m;
	cin>>n>>m>>num;
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			if(i==j){
				continue;
			}
			dis[i][j]=inf;
		}
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=num;j++){
			cin>>b[i][j]>>s[i][j];
		}
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			for(k=1;k<=num;k++){
				if(b[i][k]!=-1&&s[j][k]!=-1){
					max1[i][j]=max(max1[i][j],s[j][k]-b[i][k]);
				}
			}
		}
	}
	for(i=1;i<=m;i++){
		cin>>j>>k>>l;
		dis[j][k]=min(dis[j][k],l);
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			for(k=1;k<=n;k++){
				if(dis[j][k]>dis[j][i]+dis[i][k]){
					dis[j][k]=dis[j][i]+dis[i][k];
				}
			}
		}
	}
//	for(i=1;i<=n;i++){
//		for(j=1;j<=n;j++){
//			cout<<dis[i][j]<<' ';
//		}
//		cout<<endl;
//	}
//	for(i=1;i<=n;i++){
//		for(j=1;j<=n;j++){
//			cout<<max1[i][j]<<' ';
//		}
//		cout<<endl;
//	}
	int lef=0,rig=inf,mid;
	while(rig>lef){
		mid=(lef+rig+1)/2;
		for(i=1;i<=n;i++){
			for(j=1;j<=n;j++){
				maxdis[i][j]=max1[i][j]-dis[i][j]*mid;
				if(i==j){
					maxdis[i][i]=-inf;
				}
			}
		}
		for(i=1;i<=n;i++){
			for(j=1;j<=n;j++){
				for(k=1;k<=n;k++){
					maxdis[j][k]=max(maxdis[j][k],maxdis[j][i]+maxdis[i][k]);
				}
			}
		}
		bool cac=true;
		for(i=1;i<=n;i++){
			if(maxdis[i][i]>=0){
				lef=mid;
				cac=false;
				break;
			}
		}
		//cout<<"???"<<endl;
		if(cac){
			rig=mid-1;	
		}
	}
	cout<<lef;
}

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