Submission #1130808

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130808		nikolashami	Travelling Merchant (APIO17_merchant)	C++20	0 / 100	53 ms	2116 KiB

merchant

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N=104,inf=(1ll<<62)-62;
int og[N][N],tg[N][N],kg[N][N],bs[N][10*N][2],n,m,k;

bool ss(){
	for(int i=0;i<n;++i)if(kg[i][i]<=0)return 1;
	return 0;
}

void fw(int aa[N][N]){
	for(int kk=0;kk<n;++kk){
		for(int i=0;i<n;++i){
			for(int j=0;j<n;++j)
				aa[i][j]=min(aa[i][j],aa[i][kk]+aa[kk][j]);
		}
	}
}

bool chk(int x){
	for(int i=0;i<n;++i){
		for(int j=0;j<n;++j){
			if(og[i][j]>=inf)continue;
			int sc=og[i][j]*x;
			kg[i][j]=-(tg[i][j]-sc);
		}
	}
	fw(kg);
	return(ss());
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin>>n>>m>>k;

    for(int i=0;i<n;++i)
    	fill(og[i],og[i]+N,inf);
    
    for(int i=0;i<n;++i){
    	for(int j=0;j<k;++j)
    		cin>>bs[i][j][0]>>bs[i][j][1];
    }

    for(int i=0;i<n;++i){
    	for(int j=0;j<n;++j){
    		for(int kk=0;kk<k;++kk)
    			if(bs[j][kk][1]!=-1&&bs[i][kk][0]!=-1)
    				tg[i][j]=max(tg[i][j],bs[j][kk][1]-bs[i][kk][0]);
    	}
    }


    for(int i=0,u,v,w;i<m;++i){
    	cin>>u>>v>>w;
    	--u,--v;
    	og[u][v]=w;
    }

    fw(og);

    int l=1,r=1e9,ans=-1;
    while(l<=r){
    	int mid=(l+r)/2;
    	if(chk(mid)){
    		l=mid+1;
    		ans=mid;
    	}else
    		r=mid-1;
    }

    cout<<ans;
}

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