You need to choose a route through a network in which nodes charge you for service and each link has a possibility of failing. This network is modeled as a digraph G = (V, E), with |V | = n and |E| = m, and m n.

You are at some node s V , and you need to send a message to another node t V . Every link in this network will successfully transmit a message with probability p (0, 1), independent of all other links. Each node v V \ {s, t} will charge you c_v cents to relay your message to one of its successors. (The cost c_v may be different for each node v.) Your message needs to have a probability of at least q, for some given q (0, 1), of making it to t intact.

Design a dynamic programming algorithm to find the minimum cost of sending this message. Your algorithm should run in O(m log_p q) time. Briefly explain the reasoning behind your algorithm and your running time analysis.