{"problem":{"name":"F. Find the Inn","description":{"content":"On holidays, Bolado decided to go on an adventure. Bored with the urban life, he decided to travel to the mountains, where he'd have the time to discover new places and think in jokes. Upon his arriva","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10162F"},"statements":[{"statement_type":"Markdown","content":"On holidays, Bolado decided to go on an adventure. Bored with the urban life, he decided to travel to the mountains, where he'd have the time to discover new places and think in jokes. Upon his arrival, Bolado found himself surrounded by avast and dense forest, with trees of various types, which make his instincts lead him to the following thought.\n\n_\"Why does the pine tree never gets lost in the woods?\"_\n\n_\"Because he has a pine cone!\"_\n\n(Read the statement in Portuguese to understand the joke)\n\nGlad with the joke he made, Bolado could only think about it while looking for the inn. However, it didn't take too long until our beloved jokester noticed he was lost. Fortunately, he had a map of the area.\n\nIn the map there are N areas, numbered from 1 to N. Bolado is currently lost in the area 1 and the inn is in area N. There's also M directional paths which connect two distinct areas. Each path has also a description containing the time in minutes needed to cross it.\n\nAdditionally, because environmental preservation matters, P of the N areas have a pine tree. There are no pine trees in area 1 and area N. Whenever Bolado finds himself in one of these areas, he needs to stop and laugh for K seconds while remembering his master piece. There are T minutes left until the sun sets and Bolado wants to arrive at the inn ASAP (so he can think about inn related jokes).\n\nThe first line contains five integers, N (2 ≤ N ≤ 3 * 104), M (0 ≤ M ≤ 105), T (0 ≤ T ≤ 5 * 107), K (1 ≤ K ≤ 5 * 107), P (0 ≤ P ≤ N - 2), as described above. Then follows P integers pi (). After, there are M lines describing each path with three integers xj, yj and wj, indicating that Bolado can go from area xj to area yj in wj minutes, for 1 ≤ j ≤ M (xj ≠ yj; 1 ≤ xj, yj ≤ N and 1 ≤ wj ≤ 105).\n\nPrint the minimum time Bolado can arrive at the inn. If he can't arrive before or at the same time the sun sets, print “-1” without the quotes.\n\n## Input\n\nThe first line contains five integers, N (2 ≤ N ≤ 3 * 104), M (0 ≤ M ≤ 105), T (0 ≤ T ≤ 5 * 107), K (1 ≤ K ≤ 5 * 107), P (0 ≤ P ≤ N - 2), as described above. Then follows P integers pi (). After, there are M lines describing each path with three integers xj, yj and wj, indicating that Bolado can go from area xj to area yj in wj minutes, for 1 ≤ j ≤ M (xj ≠ yj; 1 ≤ xj, yj ≤ N and 1 ≤ wj ≤ 105).\n\n## Output\n\nPrint the minimum time Bolado can arrive at the inn. If he can't arrive before or at the same time the sun sets, print “-1” without the quotes.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N, M, T, K, P \\in \\mathbb{Z} $ be the number of areas, directional paths, time until sunset (in minutes), laughter delay per pine tree (in seconds), and number of pine tree areas, respectively.  \nLet $ P_{\\text{set}} \\subseteq \\{2, 3, \\dots, N-1\\} $ be the set of areas containing pine trees.  \nLet $ G = (V, E) $ be a directed graph where $ V = \\{1, 2, \\dots, N\\} $, and each edge $ (x_j, y_j) \\in E $ has weight $ w_j \\in \\mathbb{Z}^+ $ (travel time in minutes).  \n\n**Constraints**  \n1. $ 2 \\leq N \\leq 3 \\cdot 10^4 $  \n2. $ 0 \\leq M \\leq 10^5 $  \n3. $ 0 \\leq T \\leq 5 \\cdot 10^7 $  \n4. $ 1 \\leq K \\leq 5 \\cdot 10^7 $  \n5. $ 0 \\leq P \\leq N - 2 $  \n6. For each pine tree area $ p_i \\in P_{\\text{set}} $: $ 2 \\leq p_i \\leq N-1 $  \n7. For each edge $ (x_j, y_j, w_j) $: $ 1 \\leq x_j, y_j \\leq N $, $ x_j \\ne y_j $, $ 1 \\leq w_j \\leq 10^5 $  \n\n**Objective**  \nCompute the minimum total time (in minutes) to travel from area $ 1 $ to area $ N $, where traversing a path takes $ w_j $ minutes, and visiting any area $ p \\in P_{\\text{set}} $ adds a delay of $ \\frac{K}{60} $ minutes.  \nLet $ \\tau(p) = \\begin{cases} \\frac{K}{60} & \\text{if } p \\in P_{\\text{set}} \\\\ 0 & \\text{otherwise} \\end{cases} $.  \nFor a path $ \\pi = (v_0=1, v_1, \\dots, v_L=N) $, total time is:  \n$$\n\\sum_{i=0}^{L-1} w_{(v_i, v_{i+1})} + \\sum_{i=1}^{L-1} \\tau(v_i)\n$$  \nFind the minimum such total time. If no path exists or minimum time exceeds $ T $, output $ -1 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10162F","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}