Submission #754790

#	Time	Username	Problem	Language	Result	Execution time	Memory
754790		MISM06	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	236 ms	4232 KiB

merchant

//0 1 1 0 1
//0 1 0 0 1
//1 0 0 1 1
//0 1 1 0 1
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")

using namespace std;

#define F 			first
#define S 			second
#define pb 			push_back
#define sze			size()
#define	all(x)		x.begin() , x.end()
#define wall__		cout << "--------------------------------------\n";
#define kids		int mid = (tl + tr) >> 1, cl = v << 1, cr = v << 1 | 1
#define file_io		freopen("input.cpp", "r", stdin); freopen("output.cpp", "w", stdout);

typedef long long ll;
typedef long double dl;
typedef pair < int , int > pii;
typedef pair < int , ll > pil;
typedef pair < ll , int > pli;
typedef pair < ll , ll > pll;
typedef pair < int , pii > piii;
typedef pair < ll, pll > plll;


const ll N = 1e2 + 10, K = 1e3 + 10;
const ll mod = 1e9 + 7;
const ll inf = 2e18;
const ll rinf = -2e16;
const ll INF = 1e9 + 10;
const ll rINF = -1e9 - 10;
const ll lg = 32;

int n, m, k;
ll b[N][K], s[N][K], dis[N][N], pf[N][N], dist[N][N];

inline bool check (ll mean) {
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			ll ch = inf / mean;
			dist[i][j] = pf[i][j] - (mean * min(ch, dis[i][j]));
		}
	}
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				dist[i][j] = max(dist[i][k] + dist[k][j], dist[i][j]);
			}
		}
	}
	for (int i = 1; i <= n; i++) if (dist[i][i] >= 0) return 1;
	return 0;

}

void solve () {

	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			cin >> b[i][j] >> s[i][j];
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) dis[i][j] = inf;
	}
	for (int i = 1; i <= m; i++) {
		int v, u, w; cin >> v >> u >> w;
		dis[v][u] = w;
	}
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			pf[i][j] = 0;
			for (int x = 1; x <= k; x++) if (s[j][x] != -1 && b[i][x] != -1) pf[i][j] = max(pf[i][j], s[j][x] - b[i][x]);
		}
	}
	for (int i = 1; i <= n; i++) dis[i][i] = inf;
	ll l = 0, r = 1e17, mid;
	while (r - l > 1) {
		mid = (r + l) / 2ll;
		if (check(mid)) l = mid;
		else r = mid;
	}
	cout << l << '\n';

}


int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	int t = 1;
	// cin >> t;
	while (t--) {solve();}
    return 0;
}
/*
4 5 2
10 9 5 2
6 4 20 15
9 7 10 9
-1 -1 16 11
1 2 3
2 3 3
1 4 1
4 3 1
3 1 1

*/
//shrek will AC this;

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