Submission #246827

#	Time	Username	Problem	Language	Result	Execution time	Memory
246827		kshitij_sodani	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	77 ms	3772 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
//#define endl '\n'
llo n,m,k;
llo dist[101][101];
llo dist2[101][101];

llo min2(llo aa,llo bb){
	if(aa==-1){
		return bb;
	}
	else if(bb==-1){
		return aa;
	}
	return min(aa,bb);
}
llo cost[101][1000][2];
vector<pair<pair<llo,llo>,llo>> ed;
vector<pair<pair<llo,llo>,llo>> ed2;

bool check(llo mid){
	if(mid==0){
		return true;
	}
	for(llo i=0;i<n;i++){
		for(llo j=0;j<n;j++){
			dist2[i][j]=1e18;
		}
		dist2[i][i]=0;
	}
	for(auto j:ed){
		dist2[j.a.a][j.a.b]=dist[j.a.a][j.a.b]*mid-j.b;
	}
	/*for(auto j:ed2){
		if(dist2[j.a.a][j.a.b]==1e8){
			dist2[j.a.a][j.a.b]=mid*j.b;
		}
	}*/

	for(llo kk=0;kk<n;kk++){
		for(llo i=0;i<n;i++){

			for(llo j=0;j<n;j++){
				dist2[i][j]=min(dist2[i][j],dist2[i][kk]+dist2[kk][j]);
			}
		}
	}
/*	for(llo i=0;i<n;i++){
		if(dist2[i][i]<0){
			return true;
		}
	}*/
	for(llo i=0;i<n;i++){
		/*if(dist[i][i]<0){
			return true;
		}*/
		for(llo j=0;j<n;j++){

			if(i==j){
				continue;
			}
			if(dist2[i][j]+dist2[j][i]<=0){
				return true;
			}
		}
	}

	return false;


}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>m>>k;
	for(llo i=0;i<n;i++){
		for(llo j=0;j<n;j++){
			dist[i][j]=-1;
		}
		dist[i][i]=0;
	}
	for(llo i=0;i<n;i++){
		for(llo j=0;j<k;j++){
			cin>>cost[i][j][0]>>cost[i][j][1];
		}
	}
	for(llo i=0;i<m;i++){
		llo aa,bb,cc;
		cin>>aa>>bb>>cc;
		ed2.pb({{aa-1,bb-1},cc});
		dist[aa-1][bb-1]=min2(dist[aa-1][bb-1],cc);
	}
	for(llo kk=0;kk<n;kk++){
		for(llo i=0;i<n;i++){
			for(llo j=0;j<n;j++){
				if(dist[i][kk]==-1 or dist[kk][j]==-1){
					continue;
				}
				dist[i][j]=min2(dist[i][j],dist[i][kk]+dist[kk][j]);
			}
		}
	}
	/*	for(llo i=0;i<n;i++){
			for(llo j=0;j<n;j++){
				cout<<dist[i][j]<<",";
			}
			cout<<endl;
		}
	
*/

	
	for(llo i=0;i<n;i++){
		for(llo j=0;j<n;j++){
			if(i==j){
				continue;
			}
			llo xx=0;
			for(llo kk=0;kk<k;kk++){
				if(cost[i][kk][0]==-1 or cost[j][kk][1]==-1){
					continue;
				}
				xx=max(xx,-cost[i][kk][0]+cost[j][kk][1]);
			}
			if(dist[i][j]!=-1){
				ed.pb({{i,j},xx});
		//		cout<<i<<","<<j<<","<<xx<<endl;
			}
		}
	}
	llo low=0;
	llo high=1e9;
	while(low<high-1){
		llo mid=(low+high)/2;
		if(check(mid)){
			low=mid;
		}
		else{
			high=mid;
		}
	}
	for(llo i=high;i>=low;i--){
		if(check(i)){
			cout<<i<<endl;
			return 0;
		}
	}
	return 0;
}

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