Submission #246856

#	Time	Username	Problem	Language	Result	Execution time	Memory
246856		kshitij_sodani	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	90 ms	4344 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];
llo cost2[101][101];
vector<pair<pair<llo,llo>,llo>> ed;
//vector<pair<pair<llo,llo>,llo>> ed2;
//llo vis[101][101];
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]=min((llo)(LLONG_MAX/2/mid),dist[i][j])*mid-cost2[i][j];
		}
	}
	/*for(auto j:ed){
		dist2[j.a.a][j.a.b]=min((llo)(LLONG_MAX/mid/2),dist[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;
		}
		continue;
	}

	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]=1e18;
		}
	}

	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;
		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++){
				dist[i][j]=min(dist[i][j],dist[i][kk]+dist[kk][j]);
			}
		}
	}
	
	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]);
			}
			cost2[i][j]=xx;
		//	ed.pb({{i,j},xx});
		}
	}
	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: 12 / 12
• Subtask 2: 21 / 21
• Subtask 3: 33 / 33
• Subtask 4: 34 / 34