This problem involves a graph in which each edge e has an associated length L(e) and fun value F(e). Our goal is to find a directed cycle C minimizing L(C) / F(C), where L(C) denotes the total length of all edges in C and F(C) denotes the total fun value of all edges in C (note: the actual problem asks us to maximize F(C) / L(C), but I've converted it to a minimization problem since this is more common when we discuss shortest path type problems).
To solve this problem quickly, we employ a common trick: binary search on the answer. Let us make a guess that the answer is X. By running one instance of the Bellman-Ford shortest path algorithm (in O(LP) time), we will be able to tell if this guess is too high or too low, thereby homing in on the correct answer. The one feature of the Bellman-Ford algorithm we use here is the fact that it can detect whether or not a negative-length direct cycle exists in a graph (we won't go into how this is done here, since this is a common algorithm).
How can negative cycle detection tell us if our guess X is too high or too low? Well, we would like to check if the minimum value of L(C)/F(C) over all cycles C is less than X (i.e., if there exists a cycle C such that L(C)/F(C) <= X). If so, then our guess is too high; otherwise it is too low. But asking whether there exists a cycle C such that L(C)/F(C) <= X is the same as asking whether there exists a cycle C such that L(C) <= X F(C), which is the same as asking whether there exists a cycle C such that L(C) - X F(C) <= 0. So if we define the cost of each edge e as Z(e) = L(e) - X F(e), then this turns into a negative cycle detection problem with respect to the Z(e)'s!
Below is Chinese Junior Danqi Chen's full-credit beautifully formatted PASCAL solution (this is precisely as she submitted it) which might or might not match the description above.
program sightsee;
const
finp = 'sightsee.in';
fout = 'sightsee.out';
maxn = 1000 + 5;
eps = 1e-4;
type
nodeptr = ^node;
node = record
p, len : longint;
next : nodeptr;
end;
var
hash : array [1 .. maxn] of boolean;
queue, edge : array [1 .. maxn] of longint;
dist : array [1 .. maxn] of extended;
a : array [1 .. maxn] of nodeptr;
cost : array [1 .. maxn] of longint;
n, m : longint;
procedure create(x, y, c : longint);
var
tmp : nodeptr;
begin
new(tmp); tmp ^.p := y; tmp ^. len := c;
tmp ^.next := a[x]; a[x] := tmp;
end;
procedure init;
var
i : longint;
x, y, c : longint;
begin
read(n, m);
for i := 1 to n do read(cost[i]);
for i := 1 to n do a[i] := nil;
for i := 1 to m do
begin
read(x, y, c);
create(x, y, c);
end;
end;
function nxt(i : longint): longint;
begin
if i = maxn then nxt := 1 else nxt := i + 1;
end;
function check(limit : extended): boolean;
var
h, t, i : longint;
tmp : nodeptr;
v : extended;
begin
check := true;
fillchar(hash, sizeof(hash), false);
h := 0; t := 0;
for i := 1 to n do
begin
inc(t); queue[t] := i; hash[i] := true;
dist[i] := 0; edge[i] := 0;
end;
while (h <> t) do
begin
h := nxt(h);
tmp := a[queue[h]];
while (tmp <> nil) do
begin
v := tmp ^. len * limit - cost[tmp^.p];
if (dist[queue[h]] + v < dist[tmp^.p]) then
begin
dist[tmp^.p] := dist[queue[h]] + v;
edge[tmp^.p] := edge[queue[h]] + 1;
if edge[tmp ^. p] > n then exit;
if not hash[tmp^.p] then
begin
t := nxt(t);
queue[t] := tmp^. p;
hash[tmp ^.p] := true;
end;
end;
tmp := tmp ^. next;
end;
hash[queue[h]] := false;
end;
check := false;
end;
procedure work;
var
l, r, mid : extended;
begin
l := 0; r := 1000;
while (r - l > eps) do
begin
mid := (l + r) / 2;
if check(mid) then l := mid else r := mid;
end;
writeln(l : 0 : 2);
end;
begin
assign(input, finp); reset(input);
assign(output, fout); rewrite(output);
init;
work;
close(input); close(output);
end.