Submission #754793

#	Time	Username	Problem	Language	Result	Execution time	Memory
754793		MISM06	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	132 ms	2172 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 = 1e18;
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];
int st[N], en[N], timer, g[N][N];
 
bool dfs (int v, int p) {
	st[v] = ++timer;
	bool res = 0;
	for (int u = 0; u <= n; u++) {
		if (g[v][u] == 0) continue;
		if (st[u] == 0) res |= dfs(u, v);
		else if (en[u] == 0) return true;
	}
	en[v] = timer;
	return res;
}
inline bool check (ll mean) {
	fill(dist, dist + (n + 1), 0);
	ll ch = inf / mean;
	for (int k = 1; k < n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (i == j || dis[i][j] >= inf) continue;
				ll w = pf[i][j] - (mean * min(ch, dis[i][j])); w *= -1;
				if (dist[i] + w < dist[j]) dist[j] = dist[i] + w;
			}
		}
	}
	
	for (int i = 1; i <= n; i++) {
		if (dist[0] < dist[i]) return 1;
		if (dist[0] == dist[i]) g[0][i] = 1;
		else g[0][i] = 0;
	}
	st[0] = en[0] = 0;
	for (int i = 1; i <= n; i++) {
		st[i] = en[i] = 0;
		for (int j = 1; j <= n; j++) {
			if (i == j || dis[i][j] >= inf) {
				g[i][j] = 0;
				continue;
			}
			ll w = pf[i][j] - (mean * min(ch, dis[i][j])); w *= -1;
			if (dist[i] + w < dist[j]) return 1;
			if (dist[i] + w == dist[j]) g[i][j] = 1;
			else g[i][j] = 0;
		}
	}
	return dfs(0, -1);
}
 
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]);
		}
	}
	ll l = 0, r = 1e15, 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