Submission #1133208

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133208		Math4Life2020	Travelling Merchant (APIO17_merchant)	C++20	100 / 100	876 ms	2320 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>; using ld = long double;

const ll Nm = 105; const ll Km = 1005; const ll INF = 1e18; const ld INFD = 1e18;
ll dst[Nm][Nm]; //distance (aka time)
ll pft[Nm][Nm]; //profit
ll B[Nm][Km]; ll S[Nm][Km];
ll N;

bool qry(ld av) {
	ld dnew[N][N];
	for (int i=0;i<N;i++) {
		for (int j=0;j<N;j++) {
			if (dst[i][j]==INF) {
				dnew[i][j]=INFD;
			} else {
				dnew[i][j]=av*(ld)dst[i][j]-(ld)pft[i][j];
			}
		}
	}
	for (int k=0;k<N;k++) {
		for (int i=0;i<N;i++) {
			for (int j=0;j<N;j++) {
				if (dnew[i][k]!=INFD && dnew[k][j]!=INFD) {
					dnew[i][j]=min(dnew[i][j],dnew[i][k]+dnew[k][j]);
				} 
			}
		}
	}
	for (int k=0;k<N;k++) {
		for (int i=0;i<N;i++) {
			for (int j=0;j<N;j++) {
				if (dnew[i][k]!=INFD && dnew[k][j]!=INFD) {
					dnew[i][j]=min(dnew[i][j],dnew[i][k]+dnew[k][j]);
				} 
			}
		}
	}
	for (int i=0;i<N;i++) {
		if (dnew[i][i]<(-(ld)(1e-10))) {
			return 1;
		}
	}
	return 0;
}

int main() {
	ll M,K; cin >> N >> M >> K;
	for (int i=0;i<N;i++) {
		for (ll k=0;k<K;k++) {
			cin >> B[i][k] >> S[i][k];
		}
	}
	for (int i=0;i<N;i++) {
		for (int j=0;j<N;j++) {
			pft[i][j]=0;
			dst[i][j]=INF;
			if (i!=j) {
				for (int k=0;k<K;k++) {
					if (S[j][k]!=-1 && B[i][k]!=-1) {
						pft[i][j]=max(pft[i][j],S[j][k]-B[i][k]);
					}
				}
			}
		}
	}
	for (ll m=0;m<M;m++) {
		ll v,p,t; cin >> v >> p >> t; v--; p--;
		dst[v][p]=min(dst[v][p],t);
	}
	for (int k=0;k<N;k++) {
		for (int i=0;i<N;i++) {
			for (int j=0;j<N;j++) {
				if (dst[i][k]!=INF && dst[k][j]!=INF) {
					dst[i][j]=min(dst[i][j],dst[i][k]+dst[k][j]);
				}
			}
		}
	}
	ld ansmin = 0; ld ansmax = 1e10;
	while ((ansmax-ansmin)>=((ld)1e-10)) {
		ld anst = (ansmax+ansmin)/2;
		if (qry(anst)) {
			ansmin = anst;
		} else {
			ansmax = anst;
		}
	}
	cout << (ll) (ansmax+(1e-10)) <<"\n";
}

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