{"problem":{"name":"K. Police Catching Thief","description":{"content":"A thief is trying to escape the holds of the police through a city. Let’s assume we represent our city by a weighted undirected connected graph(with no self-loops and multi-edges) with N nodes and M e","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10058K"},"statements":[{"statement_type":"Markdown","content":"A thief is trying to escape the holds of the police through a city. Let’s assume we represent our city by a weighted undirected connected graph(with no self-loops and multi-edges) with N nodes and M edges.\n\nThief is currently at vertex numbered S and needs to reach vertex numbered D. Thief moves with constant speed VT = 1.\n\nK policemen are initially located in K distinct locations denoted by A1, A2, ..., AK. Each policeman has a constant speed of VP = 1.\n\nTo help policemen, a single power booster have been provided to them. This power booster can be availed once from any one of the Q distinct ‘special’ nodes B1, B2, ..., BQ. Property of this power booster being that it doubles the speed of the policeman who avails this power booster.\n\nNote: A policeman can choose not to avail the power booster even if he is at a ‘special’ node.\n\nYou have to print the shortest time in which thief can escape the police regardless of whatever path the police might take. If he can’t reach the destination, output  - 1.\n\nFirst line contains N and M, the number of nodes and number of edges respectively.\n\nEach of the next M lines contain integers u v and w denoting an undirected edge between nodes numbered u and v, w being the weight of the edge. Next line contains a single integer K denoting number of different policemen. Next line contains K space separated integers denoting the distinct locations A1, A2, ..., AK.\n\nNext line contains a single integer Q denoting number of ‘special’ nodes. Next line contains Q distinct space separated integers denoting the locations B1, B2, ..., BQ.\n\nNext line contains two distinct integers S and D denoting the source and destination of the thief.\n\nFor each test case print the minimum time required for thief to escape(if possible). Else, output  - 1.\n\n*Constraints* \n\nExample1:\n\nPolice takes the path 3 to 0 to 1 availing the power booster at node 0. Even though both policeman and thief reach the destination at same time, police catches thief.\n\nExample2:\n\nWhichever policeman uses the power booster, thief will be able to escape in 2 seconds.\n\n## Input\n\nFirst line contains N and M, the number of nodes and number of edges respectively.Each of the next M lines contain integers u v and w denoting an undirected edge between nodes numbered u and v, w being the weight of the edge. Next line contains a single integer K denoting number of different policemen. Next line contains K space separated integers denoting the distinct locations A1, A2, ..., AK.Next line contains a single integer Q denoting number of ‘special’ nodes. Next line contains Q distinct space separated integers denoting the locations B1, B2, ..., BQ.Next line contains two distinct integers S and D denoting the source and destination of the thief.\n\n## Output\n\nFor each test case print the minimum time required for thief to escape(if possible). Else, output  - 1.*Constraints*   1  ≤  N  ≤  105  M  ≤  min(2 * 105, N * (N - 1) / 2)  0  ≤  u, v, S, D, Ai, Bi < N  0  ≤  Y  ≤  109  1  ≤  X, u, v  ≤  N  0  ≤  K, Q  ≤  N  1  ≤  w  ≤  109 \n\n[samples]\n\n## Note\n\nExample1:Police takes the path 3 to 0 to 1 availing the power booster at node 0. Even though both policeman and thief reach the destination at same time, police catches thief.Example2:Whichever policeman uses the power booster, thief will be able to escape in 2 seconds.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ G = (V, E) $ be a weighted undirected connected graph with $ |V| = N $ nodes and $ |E| = M $ edges.  \nLet $ w: E \\to \\mathbb{R}^+ $ denote the edge weight function.  \n\nLet $ S, D \\in V $ be the thief’s start and destination nodes.  \nLet $ V_T = 1 $ be the thief’s constant speed.  \nLet $ V_P = 1 $ be the base speed of each policeman.  \nLet $ K \\in \\mathbb{Z}^+ $ be the number of policemen, with initial positions $ A = \\{A_1, A_2, \\dots, A_K\\} \\subseteq V $, all distinct.  \nLet $ Q \\in \\mathbb{Z}^+ $ be the number of special nodes $ B = \\{B_1, B_2, \\dots, B_Q\\} \\subseteq V $, all distinct.  \nA policeman may use the power booster **at most once**, and **only if located at a node in $ B $**, doubling their speed to $ 2 $.  \n\n**Constraints**  \n1. $ 1 \\le N, M \\le 10^5 $  \n2. Edge weights are positive real numbers.  \n3. $ 1 \\le K \\le N $, $ 1 \\le Q \\le N $, $ S \\ne D $, all positions distinct as specified.  \n\n**Objective**  \nCompute the **minimum time $ T^* $** such that the thief can travel from $ S $ to $ D $ along some path $ P $ with total time $ T_P = \\text{dist}_G(S, D) $, and for **every possible strategy** the policemen may adopt (including choice of whether/where to use the booster), **at least one policeman** reaches $ D $ **no earlier than** the thief.  \n\nThat is, find:  \n$$\nT^* = \\min_{P: S \\to D} \\left( \\text{length}(P) \\right)\n\\quad \\text{such that} \\quad\n\\forall \\text{policeman strategies}, \\; \\min_{i \\in [K]} \\left( \\text{time}_i \\right) \\ge \\text{length}(P)\n$$  \nwhere $ \\text{time}_i $ is the minimum time policeman $ i $ can reach $ D $, possibly using the booster optimally (i.e., choosing whether and where to use it).  \n\nIf no such path exists (i.e., thief cannot reach $ D $), output $ -1 $.  \n\n**Note**: The thief escapes **only if** he arrives at $ D $ **strictly before** all policemen (even if one policeman arrives at the same time, he is caught).  \nThus, we require:  \n$$\nT^* < \\min_{\\text{policeman strategies}} \\max_{i \\in [K]} \\left( \\text{min time for policeman } i \\text{ to reach } D \\right)\n$$  \nBut since police act optimally to **catch** the thief, we must compute:  \n$$\nT^* = \\min \\left\\{ t \\,\\middle|\\, \\exists \\text{ path } P \\text{ from } S \\to D \\text{ of length } t, \\text{ and } \\forall \\text{ choices of booster usage by police}, \\; \\max_{i \\in [K]} \\text{time}_i > t \\right\\}\n$$  \nEquivalently, define $ T_{\\text{catch}} = \\min_{i \\in [K]} \\left( \\min_{\\text{booster usage}} \\text{time}_i \\right) $ — the **minimum time any policeman can reach $ D $** using optimal booster usage.  \nThen the thief must reach $ D $ in time **strictly less than** $ T_{\\text{catch}} $.  \n\nThus:  \nLet $ d(u, v) $ be shortest path distance in $ G $.  \nFor each policeman $ i $ at position $ A_i $, define:  \n$$\nt_i = \\min \\left( d(A_i, D), \\min_{b \\in B} \\left( d(A_i, b) + \\frac{d(b, D)}{2} \\right) \\right)\n$$  \nThen the **best possible time for any policeman to reach $ D $** is:  \n$$\nT_{\\text{police}} = \\min_{i \\in [K]} t_i\n$$  \nThief’s shortest path time:  \n$$\nT_{\\text{thief}} = d(S, D)\n$$  \nThen:  \n- If $ T_{\\text{thief}} = \\infty $, output $ -1 $.  \n- Else, if $ T_{\\text{thief}} < T_{\\text{police}} $, output $ T_{\\text{thief}} $.  \n- Else, output $ -1 $.  \n\n**Final Formal Statement**  \n$$\n\\boxed{\nT^* =\n\\begin{cases}\nd(S, D) & \\text{if } d(S, D) < \\min_{i=1}^K \\min \\left( d(A_i, D), \\min_{b \\in B} \\left( d(A_i, b) + \\frac{d(b, D)}{2} \\right) \\right) \\\\\n-1 & \\text{otherwise}\n\\end{cases}\n}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10058K","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}