Person $A$ is chasing person $B$. Both people can only travel between $n$ vertices of a graph by running through one of $m$ one-way pipes labelled $1,2,\cdots, m$. For each pipe we know the starting and ending vertex. Each pipe has two values $A_i, B_i$ which are positive real numbers and represent the multipliers of person $A$'s and $B$'s heights as they run through the pipe. For example, if person A and person B currently both have height $2$, if they run through the pipe with $A_i =1, B_i = 2$, then person B will now have height $4$ while person A will have height $2$.

A starts running at a vertex s while B starts at s an instant later and will chase A at the same speed later. You can treat A and B as a single object whose trajectory is entirely determined by A.

Given the graph (with no duplicate edges or self-loops) and the starting vertex s, how can I determine in O(nm) time or faster if it's possible for A to lead B through a sequence of pipes so that A gets infinitely larger than B? Provide a justification for the algorithm.

I was thinking of creating a new graph where there is a negative weight cycle if and only if it's possible for A to be infinitely larger than B after travelling through a sequence of pipes. Then I could use the Bellman Ford algorithm to solve the problem in $O(nm)$ time. But I'm not sure how to find this graph.

Person $A$ is chasing person $B$. Both people can only travel between $n$ vertices of a graph by running through one of $m$ one-way pipes labelled $1,2,\cdots, m$. For each pipe we know the starting and ending vertex. Each pipe has two values $A_i, B_i$ which are positive real numbers and represent the multipliers of person $A$'s and $B$'s heights as they run through the pipe. For example, if person $A$ and person $B$ currently both have height $2$, if they run through the pipe with $A_i =1, B_i = 2$, then person B will now have height $4$ while person $A$ will have height $2$.

$A$ starts running at a vertex $s$ while $B$ starts at s an instant later and will chase $A$ at the same speed later. You can treat $A$ and $B$ as a single object whose trajectory is entirely determined by $A$.

Given the graph (with no duplicate edges or self-loops) and the starting vertex $s$, how can I determine in $O(nm)$ time or faster if it's possible for $A$ to lead $B$ through a sequence of pipes so that $A$ gets infinitely larger than $B$? Provide a justification for the algorithm.

I was thinking of creating a new graph where there is a negative weight cycle if and only if it's possible for $A$ to be infinitely larger than $B$ after travelling through a sequence of pipes. Then I could use the Bellman Ford algorithm to solve the problem in $O(nm)$ time. But I'm not sure how to find this graph.

Person $A$ is chasing person $B$. Both people can only travel between $n$ vertices of a graph by running through one of $m$ one-way pipes labelled $1,2,\cdots, m$. For each pipe we know the starting and ending vertex. Each pipe has two values $A_i, B_i$ which are positive real numbers and represent the multipliers of person $A$'s and $B$'s heights as they run through the pipe. For example, if person A and person B currently both have height $2$, if they run through the pipe with $A_i =1, B_i = 2$, then person B will now have height $4$ while person A will have height $2$.

A starts running at a vertex s while B starts at s an instant later and will chase A at the same speed later. You can treat A and B as a single object whose trajectory is entirely determined by A.

Given the graph (with no duplicate edges or self-loops) and the starting vertex s, how can I determine in O((n+m)^10) time or faster if it's possible for A to lead B through a sequence of pipes so that A gets infinitely larger than B? Provide a justification for the algorithm.

I was thinking of creating a new graph where there is a negative weight cycle if and only if it's possible for A to be infinitely larger than B after travelling through a sequence of pipes. Then I could use the Bellman Ford algorithm to solve the problem in $O(nm)$ time. But I'm not sure how to find this graph.

Person $A$ is chasing person $B$. Both people can only travel between $n$ vertices of a graph by running through one of $m$ one-way pipes labelled $1,2,\cdots, m$. For each pipe we know the starting and ending vertex. Each pipe has two values $A_i, B_i$ which are positive real numbers and represent the multipliers of person $A$'s and $B$'s heights as they run through the pipe. For example, if person A and person B currently both have height $2$, if they run through the pipe with $A_i =1, B_i = 2$, then person B will now have height $4$ while person A will have height $2$.

A starts running at a vertex s while B starts at s an instant later and will chase A at the same speed later. You can treat A and B as a single object whose trajectory is entirely determined by A.

Given the graph (with no duplicate edges or self-loops) and the starting vertex s, how can I determine in O(nm) time or faster if it's possible for A to lead B through a sequence of pipes so that A gets infinitely larger than B? Provide a justification for the algorithm.

I was thinking of creating a new graph where there is a negative weight cycle if and only if it's possible for A to be infinitely larger than B after travelling through a sequence of pipes. Then I could use the Bellman Ford algorithm to solve the problem in $O(nm)$ time. But I'm not sure how to find this graph.