DP Made Easy
All submissions for this problem are available.
Consider a 2 dimensional minimum Dynamic Programming problem represented as DP[i][j].
Initially we are given N quadratic functions of the form ƒi(x) = ai*x2 + bi*x1 + ci, where ai >= bi >= ci >= 0.
- Transition of the DP in 1st dimension is given as some transition pairs with a cost associated with it.
For example, given i one can transit to v1, v2, v3 ... vx with cost w1, w2, w3 ... wx respectively then
DP[i][j] = min( DP[vk][j] + wk ) ∀ k <= x and ∀ j.
If it is possible to transit from i to vk with cost wk then it is also possible to transit from vk to i with cost wk.
- Transition in 2nd dimension is given as -
DP[i][j] = min ( DP[i][j-d] + ƒi(d) ) ∀ d <= j-1.
There are Q queries, each query representing change in ƒi(x) and is given as i ai bi ci, where ai >= bi >= ci >= 0. After this query ƒi(x) = ai*x2 + bi*x1 + ci.
For each query find DP[N][N].
Input Format:First line of the input contains 3 space separated integers denoting N, M, Q where M denotes number of valid transition pairs given.
Next M lines contains 3 space separated integers u, v, w which denotes we can transit from u to v and from v to u in the first dimension with cost w.
Each of the next N lines contains 3 space separated integers ai, bi, ci representing ƒi(x). Next Q lines contains queries as described in the problem statement.
Output Format:After each query print a line containing the value of DP[N][N].
- 1<= N <= 100000
- 1<= M <= 400000
- 1<= Q <= 100000
- 0<= ci <= bi <= ai <= 100000
Sample Input:-2 1 2
2 1 5
1 1 1
5 4 1
2 2 2 1
1 3 2 2
|Tags||gvaibhav21, inso2018, insomnia18, multiset, shortest-path|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions