Submission #1014928

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014928		idiotcomputer	Travelling Merchant (APIO17_merchant)	C++11	100 / 100	66 ms	4248 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
#define ll long long int 
#define pb push_back
#define sz size 
#define pii pair<ll,ll>
#define f first
#define s second

const int mxN = 100;
const int mxK = 1e3;
const ll inf = 1e18;
int n,m,k;

ll d[mxN][mxN];
ll p[mxN][mxN];
pii vals[mxN][mxK];

bool solve(ll x){
	ll d2[n][n];
	for (int i =0; i < n; i++)	for (int j =0; j < n; j++){
		if (d[i][j] == inf || d[i][j] >= inf/x) d2[i][j] = inf;
		else d2[i][j] = d[i][j]*x-p[i][j];
	}
	for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++){
		if (d2[i][k] != inf && d2[k][j] != inf) d2[i][j] = min(d2[i][j],d2[i][k]+d2[k][j]);
	}

	for (int i = 0; i < n; i++) if (d2[i][i] <= 0) return true;

	return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m >> k;
	for (int i = 0; i < n; i++) for (int j = 0; j < k; j++) cin >> vals[i][j].f >> vals[i][j].s;

	for (int i =0; i < n; i++) for (int j =0; j < n; j++) d[i][j] = inf;

	ll v,w,t;
	for (int i = 0; i < m; i++){
		cin >> v >> w >> t;
		v -= 1;
		w -= 1;
		d[v][w] = min(d[v][w],(ll)t);
	} 

	for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++){
		if (d[i][k] != inf && d[k][j] != inf) d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
	}
/*	for (int i =0; i < n; i++){
		for (int j =0; j < n; j++) cout << d[i][j] << " ";
		cout << '\n';
	}*/
	memset(p,0,sizeof(p));
	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) for (int t = 0; t < k; t++){
		if (vals[i][t].f == -1 || vals[j][t].s == -1) continue;
		p[i][j] = max(p[i][j],vals[j][t].s - vals[i][t].f);
	}

/*	for (int i =0; i < n; i++){
		for (int j = 0; j < n; j++) cout << p[i][j] << " ";
		cout << '\n';
	}
*/
	ll l = 0;
	ll r = 1e9+1;
	ll c;
	while (r-l>1){
		c = (l+r)/2;
		if (solve(c)) l = c;
		else r = c;
	}
	cout << l << "\n";
	return 0;
}

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