Submission #1089798

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089798		alexander707070	Travelling Merchant (APIO17_merchant)	C++14	21 / 100	1081 ms	11348 KiB

merchant

#include<bits/stdc++.h>
#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][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++){
			dp[i][f][1]=-inf;
			
			for(int p=1;p<=n;p++){
				if(cost[i][p]==0)continue;
				dp[i][f][1]=max(dp[i][f][1],cost[i][p]-(dist[i][p]+dist[p][f])*x);
			}
		}
	}

	for(int w=2;w<=n;w++){
		for(int i=1;i<=n;i++){
			for(int f=1;f<=n;f++){
				dp[i][f][w]=-inf;

				for(int p=1;p<=n;p++){
					dp[i][f][w]=max(dp[i][f][w],dp[i][p][w-1]+dp[p][f][1]);
				}
			}
		}
	}

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

	return false;
}

int bin(){
	int l=0,r=inf,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(){

	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: 0 / 33
• Subtask 4: 0 / 34