{"problem":{"name":"D. Desolation of Smaug","description":{"content":"Frodo Baggins is trying to run from the fury of Smaug. Let’s assume we represent our city by a weighted undirected connected graph(with no self-loops and multi-edges) with N nodes and N edges. You wi","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10058D"},"statements":[{"statement_type":"Markdown","content":"Frodo Baggins is trying to run from the fury of Smaug. Let’s assume we represent our city by a weighted undirected connected graph(with no self-loops and multi-edges) with N nodes and N edges.\n\nYou will be given Q queries of form St, De, S, Vf, VS which denotes: \n\nFrodo is currently at node St and needs to reach node De. He moves with constant velocity Vf. Smaug is currently at node S and he moves with constant velocity VS. Print \"YES\"(quotes for clarity), if Frodo can reach destination without being caught by Smaug no matter what path Smaug takes. Else print \"NO\"(quotes for clarity).\n\nNote: If Frodo reaches at destination at same time as Smaug, print \"NO\".\n\nFirst line contains N and Q, the number of nodes and number of queries respectively. Each of the next N lines contain integers u, v and w denoting an undirected edge between nodes numbered u and v, w being the weight of the edge.\n\nEach of the next Q lines contain queries.\n\nFor each query print the required answer in one line.\n\n*Constraints* \n\n## Input\n\nFirst line contains N and Q, the number of nodes and number of queries respectively. Each of the next N lines contain integers u, v and w denoting an undirected edge between nodes numbered u and v, w being the weight of the edge.Each of the next Q lines contain queries.\n\n## Output\n\nFor each query print the required answer in one line.*Constraints*   1 ≤ N, Q ≤ 105  1 ≤ u, v, St, De, S ≤ N  1 ≤ VF, VS, w ≤ 1000 \n\n[samples]","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| = N $ edges.  \nLet $ w: E \\to \\mathbb{R}^+ $ be the edge weight function (positive real numbers).  \n\nFor each query $ q \\in \\{1, \\dots, Q\\} $:  \n- $ s_t^{(q)} \\in V $: Frodo’s starting node.  \n- $ d^{(q)} \\in V $: Frodo’s destination node.  \n- $ v_f^{(q)} \\in \\mathbb{R}^+ $: Frodo’s constant velocity.  \n- $ s^{(q)} \\in V $: Smaug’s starting node.  \n- $ v_s^{(q)} \\in \\mathbb{R}^+ $: Smaug’s constant velocity.  \n\n**Constraints**  \n1. $ 1 \\le N \\le \\text{upper bound} $ (not specified, but implied by context).  \n2. $ 1 \\le Q \\le \\text{upper bound} $ (not specified).  \n3. Edge weights $ w(e) > 0 $ for all $ e \\in E $.  \n4. Velocities $ v_f^{(q)} > 0 $, $ v_s^{(q)} > 0 $ for all queries.  \n\n**Objective**  \nFor each query $ q $, compute:  \n- $ D_f^{(q)} = \\min_{P \\in \\mathcal{P}(s_t^{(q)}, d^{(q)})} \\sum_{e \\in P} w(e) $: shortest path distance from $ s_t^{(q)} $ to $ d^{(q)} $.  \n- $ D_s^{(q)} = \\min_{P \\in \\mathcal{P}(s^{(q)}, d^{(q)})} \\sum_{e \\in P} w(e) $: shortest path distance from $ s^{(q)} $ to $ d^{(q)} $.  \n\nLet $ t_f^{(q)} = \\frac{D_f^{(q)}}{v_f^{(q)}} $: Frodo’s minimum time to reach $ d^{(q)} $.  \nLet $ t_s^{(q)} = \\frac{D_s^{(q)}}{v_s^{(q)}} $: Smaug’s minimum time to reach $ d^{(q)} $.  \n\nOutput:  \n$$\n\\begin{cases}\n\\text{YES} & \\text{if } t_f^{(q)} < t_s^{(q)} \\\\\n\\text{NO} & \\text{otherwise}\n\\end{cases}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10058D","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}