Submission #1089804

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089804		alexander707070	Travelling Merchant (APIO17_merchant)	C++14	54 / 100	84 ms	3152 KiB

merchant

#include<bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#define MAXN 107
using namespace std;

const long long inf=1e9;

int n,m,k,a,b,c,s[MAXN][2007],cost[MAXN][MAXN];
long long dist[MAXN][MAXN];

long long dp[MAXN][MAXN];

void precalc(){

	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int f=1;f<=n;f++){
				if(dist[i][k]+dist[k][f]<dist[i][f])dist[i][f]=dist[i][k]+dist[k][f];
			}
		}
	}

	for(int i=1;i<=n;i++){
		for(int f=1;f<=n;f++){
			cost[i][f]=0;

			for(int t=1;t<=2*k;t+=2){
				if(s[i][t]==-1 or s[f][t+1]==-1)continue;
				cost[i][f]=max(cost[i][f],-s[i][t]+s[f][t+1]);
			}
		}
	}
}

bool ok(long long x){

	for(int i=1;i<=n;i++){
		for(int f=1;f<=n;f++){
			if(i==f)dp[i][f]=-inf;
			else dp[i][f]=cost[i][f]-dist[i][f]*x;
		}
	}

	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int f=1;f<=n;f++){
				if(dp[i][k]+dp[k][f]>dp[i][f]){
					dp[i][f]=dp[i][k]+dp[k][f];
				}
			}
		}
	}

	for(int i=1;i<=n;i++){
		if(dp[i][i]>=0)return true;
	}

	return false;
}

int bin(){
	int l=0,r=inf+1,tt;

	while(l+1<r){
		tt=(l+r)/2;
		if(ok(tt)){
			l=tt;
		}else{
			r=tt;
		}
	}

	return l;
}

void check(){
	for(int i=1;i<=n;i++){
		for(int f=i+1;f<=n;f++){
			if(dist[i][f]+dist[f][i]<inf)return;
		}
	}

	cout<<"-1\n";
	exit(0);
}

int main(){

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin>>n>>m>>k;

	for(int i=1;i<=n;i++){
		for(int f=1;f<=2*k;f++){
			cin>>s[i][f];
		}
	}

	for(int i=1;i<=n;i++){
		for(int f=1;f<=n;f++){
			dist[i][f]=inf;
		}
		dist[i][i]=0;
	}

	for(int i=1;i<=m;i++){
		cin>>a>>b>>c;
		dist[a][b]=c;
	}

	precalc();
	check();

	cout<<bin()<<"\n";

    return 0;
}

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