# APIO 2017 - Traveling Merchant

Author: Andi Qu

First, find the maximum profit of each footpath by comparing the buying and selling prices of the endpoints for each of the $K$ items. We now have a directed graph where each edge has a profit $p$ and a time to traverse $t$.

Ratios are inconvenient, so let's consider a simpler problem: given $R$, can we find a profit cycle with profit $P$ and time $T$ such that $P/T \geq R$?

This is convenient because we can make it linear: this problem is equivalent to checking whether we can find a profit cycle with profit $P$ and time $T$ such that $P - TR \geq 0$. If we weight each edge as $p - tR$, this is equivalent to checking whether a non-negative cycle exists in the graph.

Since $R$ is good if $R + 1$ is good, we can binary search for the largest good $R$. We can then use Floyd-Warshall to check whether there is a negative cycle.

(For a similar problem, see Cruise from BkOI 2016. Beware though - it's geometry!)

## Implementation

#include <bits/stdc++.h>#define FOR(i, x, y) for (int i = x; i < y; i++)typedef long long ll;using namespace std;const ll INF = LLONG_MAX / 2;int n, m, x;ll b[101][1001], s[101][1001];ll graph[101][101], profit[101][101], graph2[101][101];

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!