Submission #1260129

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260129		ebrambill	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	88 ms	2120 KiB

merchant

//In the name of GOD

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

const long long maxN=1e2+5, maxK=1e3+5, inf=2e9;
long long n, m, k, b[maxN][maxK], s[maxN][maxK], dis[maxN][maxN], tmp[maxN][maxN], mx[maxN][maxN];

bool can(long long x){
	for (long long u=1; u<=n; u++)
		for (long long v=1; v<=n; v++)
			tmp[u][v]=(dis[u][v]!=inf ? x*dis[u][v] : inf)-mx[u][v];

	for (long long w=1; w<=n; w++)
		for (long long u=1; u<=n; u++)
			for (long long v=1; v<=n; v++)
				tmp[u][v]=min(tmp[u][v], tmp[u][w]+tmp[w][v]);
	
	for (long long v=1; v<=n; v++)
		if(tmp[v][v]<=0) return true;
	return false;
}

int main(){
	cin >>n >>m >>k;
	for (long long v=1; v<=n; v++){
		for (long long i=1; i<=k; i++)
			cin >>b[v][i] >>s[v][i];
		for (long long u=1; u<=n; u++)
			dis[u][v]=inf;
	}
	for (long long i=1, u, v, w; i<=m; i++){
		cin >>u >>v >>w;
		dis[u][v]=w;
	}

	for (long long w=1; w<=n; w++)
		for (long long u=1; u<=n; u++)
			for (long long v=1; v<=n; v++)
				dis[u][v]=min(dis[u][v], dis[u][w]+dis[w][v]);
	for (long long u=1; u<=n; u++)
		for (long long v=1; v<=n; v++)
			for (long long i=1; i<=k and dis[u][v]!=inf; i++)
				if(b[u][i]!=-1 and s[v][i]!=-1)
					mx[u][v]=max(mx[u][v], s[v][i]-b[u][i]);
	
	long long l=0, r=inf;
	while(r-l>1){
		long long mid=(r+l)>>1;
		if(can(mid)) l=mid;
		else r=mid;
	}
	cout <<l;
}

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