Submission #110975

#	Time	Username	Problem	Language	Result	Execution time	Memory
110975		nxteru	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	112 ms	4344 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<ll,ll> P;
typedef pair<ll,P> T;
#define M 1000000007
#define F first
#define S second
#define PB push_back
#define INF 1000000001
ll n,m,k,s[105][1005],b[105][1005],d[105][105];
vector<T>g[105];
bool check(ll x){
	for(int i=0;i<n;i++)for(int j=0;j<n;j++)d[i][j]=INF;
	for(int i=0;i<n;i++){
		for(int j=0;j<g[i].size();j++){
			d[i][g[i][j].F]=x*g[i][j].S.S-g[i][j].S.F;
		}
	}
	for(int l=0;l<n;l++){
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(d[i][l]!=INF&&d[l][j]!=INF)d[i][j]=min(d[i][j],d[i][l]+d[l][j]);
			}
			if(d[i][i]<=0)return true;
		}
	}
	return false;
}
int main(void){
	scanf("%lld%lld%lld",&n,&m,&k);
	for(int i=0;i<n;i++){
		for(int j=0;j<k;j++){
			scanf("%lld%lld",&s[i][j],&b[i][j]);
		}
	}
	for(int i=0;i<n;i++)for(int j=0;j<n;j++)d[i][j]=INF;
	for(int i=0;i<m;i++){
		ll v,w,t;
		scanf("%lld%lld%lld",&v,&w,&t);
		v--,w--;
		d[v][w]=t;
	}
	for(int i=0;i<n;i++)d[i][i]=0;
	for(int l=0;l<n;l++){
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				d[i][j]=min(d[i][j],d[i][l]+d[l][j]);
			}
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(i==j||d[i][j]==INF)continue;
			ll ma=0;
			for(int l=0;l<k;l++){
				if(s[i][l]!=-1&&b[j][l]!=-1){
					ma=max(ma,b[j][l]-s[i][l]);
				}
			}
			g[i].PB(T(j,P(ma,d[i][j])));
		}
	}
	ll l=0,r=INF;
	while(r-l>1){
		ll x=(l+r)/2LL;
		if(check(x))l=x;
		else r=x;
	}
	printf("%lld\n",l);
}

Compilation message (stderr)

merchant.cpp: In function 'bool check(ll)':
merchant.cpp:17:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<g[i].size();j++){
               ~^~~~~~~~~~~~
merchant.cpp: In function 'int main()':
merchant.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld",&n,&m,&k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:35:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld%lld",&s[i][j],&b[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld",&v,&w,&t);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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