Submission #262660

#	Time	Username	Problem	Language	Result	Execution time	Memory
262660		Saboon	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	102 ms	4088 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int maxn = 105;
const int maxk = 1005;
const int maxm = 10005;
const ll inf = (ll)1e18;
ll b[maxn][maxk],s[maxn][maxk];
int n,m;
pair<pair<int,int>,ll> e[maxn], E[maxn*maxn];
ll dp[maxn][maxn];
ll c[maxn][maxn];
ll sp[maxn], up[maxn];
 
bool bellman(){
	memset(sp, 63, sizeof sp);
	sp[1] = 0;
	for (int j = 1; j <= n; j++){
		for (int i = 1; i <= n*n; i++){
			int v = E[i].first.first, u = E[i].first.second;
			ll w = 1'000LL * E[i].second;
			if (sp[u] > sp[v]+w){
				sp[u] = sp[v]+w;
				up[u] = v;
			}
		}
	}	
	for (int i = 1; i <= n * n; i++){
		int v = E[i].first.first, u = E[i].first.second;
		ll w = 1'000LL * E[i].second;
		if (sp[u] > sp[v] + w)
			return true; // found negative cycle
	}
	return false;
}
 
ll mxm = 0;

bool check(ll x){
	memset(dp, 63, sizeof dp);
	for (int i = 1; i <= n; i++)
		dp[i][i] = 0;
	for (int i = 1; i <= m; i++){
		int v = e[i].first.first, u = e[i].first.second;
		ll w = e[i].second;
		dp[v][u] = x*w;
	}
	for (int k = 1; k <= n; k++)
		for (int v = 1; v <= n; v++)
			for (int u = 1; u <= n; u++)
				dp[v][u] = min(dp[v][u], dp[v][k] + dp[k][u]);
	int now = 1;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			E[now ++] = {{i, j}, dp[i][j] - c[i][j]};
	return bellman();
}
 
int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int k;
	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 <= m; i++){
		int v, u, w;
		cin >> v >> u >> w;
		e[i] = {{v, u}, w};
	}
	ll answer = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			for (int x = 1; x <= k; x++)
				if (b[i][x] != -1 and s[j][x] != -1)
					c[i][j] = max(c[i][j], s[j][x] - b[i][x]);
	ll lo = 0, hi = 1000 * 1000 * 1000 + 1;
	while (hi - lo > 1){
		ll mid = (lo + hi) >> 1;
		if (check(mid))
			lo = mid;
		else
			hi = mid;
	}
	cout << lo << endl;
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:72:5: warning: unused variable 'answer' [-Wunused-variable]
   72 |  ll answer = 0;
      |     ^~~~~~

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