Submission #383337

#	Time	Username	Problem	Language	Result	Execution time	Memory
383337		Saynaa	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	143 ms	5484 KiB

merchant

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MAXN = 1000 + 10;
const ll MAX = LLONG_MAX/2;
int n, m, pf;
ll mat[MAXN][MAXN], tmp[MAXN][MAXN], b[MAXN][MAXN], s[MAXN][MAXN], res[MAXN][MAXN];
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> m >> pf;
	for(int i = 0; i < n; i ++){
		for(int j = 0; j < n; j ++) mat[i][j] = MAX;
		for(int j = 0; j < pf; j ++)
			cin >> b[i][j] >> s[i][j];
	}
	for(int i = 0; i < m; i ++){
		int u, v;
		ll w;
		cin >> u >> v >> w, u --, v --;
		mat[u][v] = w;
	}
	for(int i = 0; i < n; i ++)
		for(int j = 0; j < n; j ++)
			for(int t = 0; t < n; t ++)
				mat[j][t] = min(mat[j][t], mat[j][i] + mat[i][t]);

	for(int i = 0; i < n; i ++)
		for(int j = 0; j < n; j ++)
			for(int t = 0; t < pf; t ++)
				if( s[j][t] != -1 && b[i][t] != -1)
					res[i][j] = max(res[i][j], s[j][t] - b[i][t]);
	
	ll l = 1, r = MAX, ans = MAX;
	while( l <= r){
		ll mid = (l + r)/2;
		for(int i = 0; i < n; i ++)
			for(int j = 0; j < n; j ++)
				tmp[i][j] = mid*min(mat[i][j], MAX/mid) - res[i][j];
		for(int i = 0; i < n; i ++)
			for(int j = 0; j < n; j ++)
				for(int t = 0; t < n; t ++)
					tmp[j][t] = min(tmp[j][t], tmp[j][i] + tmp[i][t]);
		bool dor = false;
		for(int i = 0; i < n; i ++)
			if( tmp[i][i] <= 0) dor = true;
		if( dor ) l = mid + 1;
		else r = mid - 1, ans = min(ans, mid);
	}
	cout << r << endl;

	return 0;
}

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