Submission #942588

#	Time	Username	Problem	Language	Result	Execution time	Memory
942588		vania_javai	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	66 ms	2440 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 110;
const int Maxn = 1100;
const ll inf = 1e15;
const ll M = 1e9;
const int sq = 450;
#define debug(x)  cerr << "(" << (#x) << "): " << (x) << endl
#define lc (id << 1)
#define rc (lc | 1)
#define all(x) x.begin(), x.end()
#define SZ(x) x.size()

vector<pii> edg[N];
ll dis[N], dp[N][N][2], bs[N][N], a[N][Maxn][2];
int n, q;
bool mark[N];
void min_dis(){
	///// Base:
	for(int i = 0; i < n; i++)	
		for(int j = 0; j < n; j++)
			dp[i][j][0] = dp[i][j][1] = (i != j) * inf;
			
	for(int v = 0; v < n; v++)
		for(pii p: edg[v])
			dp[v][p.first][0] = p.second; 

	////// Update: 
	for(int k = 0; k < n; k++)
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				dp[i][j][1 - k & 1] = min(dp[i][j][k & 1], dp[i][k][k & 1] + dp[k][j][k & 1]);
}

void best_sell(){
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			for(int k = 0; k < q; k++)
				if(a[i][k][0] > 0 && a[j][k][1] > 0)
					bs[i][j] = max(bs[i][j], -a[i][k][0] + a[j][k][1]);
}

bool check(ll x){
	// c / l > x;   c > x * l   x * l - c < 0;
	for(pii p: edg[0])	mark[p.first] = 1;
	for(int i = 0; i < n; i++)	if(!mark[i])	edg[0].push_back({i, inf});
	
	for(int i = 0; i < n; i++)	dis[i] = inf;
	for(int i = 1; i < n; i++)
		for(int v = 0; v < n; v++)
			for(int u = 0; u < n; u++)
				if(dp[u][v][n & 1] <= inf)
					dis[v] = min(dis[v], dis[u] + x * dp[u][v][n & 1] - bs[u][v]);
			
	
	for(int v = 0; v < n; v++)
		for(int u = 0; u < n; u++)
			if(dp[v][u][n & 1] <= inf){
			long double mn = dis[v] + x * dp[v][u][n & 1] - bs[v][u];
			if(mn < dis[u])	return 1;
		}
	return 0;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	int m;	cin>> n>> m>> q;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < q; j++)	cin>> a[i][j][0] >> a[i][j][1];
	
	for(int i = 0; i < m; i++){
		int x, y, w;	cin>> x>> y>> w;
		edg[x - 1].push_back({y - 1, w});
	}
	
	min_dis();
	best_sell();

	ll l = -1, r = 1e9 + 100;
	while(r - l > 1){
		ll mid = (l + r) >> 1;
		(check(mid)? l: r) = mid;
	}
	cout<< r;
	return 0;
} 

Compilation message (stderr)

merchant.cpp: In function 'void min_dis()':
merchant.cpp:34:16: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   34 |     dp[i][j][1 - k & 1] = min(dp[i][j][k & 1], dp[i][k][k & 1] + dp[k][j][k & 1]);
      |              ~~^~~

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