{"problem":{"name":"[ICPC 2022 Jinan R] Shortest Path","description":{"content":"You are given an undirected weighted graph $G$ with vertices $1, 2, \\ldots, n$. Please output the sum of the answers to the following $x$ questions: - The $i$-th question $(1\\le i\\le x$): What is the ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9675"},"statements":[{"statement_type":"Markdown","content":"You are given an undirected weighted graph $G$ with vertices $1, 2, \\ldots, n$. Please output the sum of the answers to the following $x$ questions:\n- The $i$-th question $(1\\le i\\le x$): What is the minimum length of path that starts at vertex $1$, ends at vertex $n$, and contains exactly $i$ edges?\n\nFor each question, if such a path does not exist, the answer is considered to be $0$. A path may use one edge multiple times. Output the answer modulo $998244353$. \n\n## Input\n\nThe first line contains one integer $T~(1 \\le T\\le 2000)$, the number of test cases.\n\nFor each test case, the first line contains three integers $n, m, x~(1\\le n\\le 2000, 0\\le m\\le 5000, 1\\le x\\le 10^9)$. Each of the next $m$ lines describes an edge of the graph. Edge $i$ is denoted by three integers $a_i, b_i, w_i$ $(1\\le a_i, b_i\\le n, 1\\le w_i\\le 10^9)$, the labels of vertices it connects and its weight. Note that self-loops and parallel edges may exist.\n\nIt is guaranteed that the sum of $n$ over all test cases is no more than $2000$ and the sum of $m$ over all test cases is no more than $5000$.\n\n## Output\n\nFor each test case, output one integer modulo $998244353$ denoting the answer.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9675","tags":["2022","O2优化","半平面交","ICPC","李超线段树","济南"],"sample_group":[["4\n3 2 10\n1 2 5\n2 3 4\n3 0 1000000000\n3 3 100\n1 2 3\n1 3 4\n2 3 5\n4 6 1000000000\n1 2 244\n1 2 325\n1 4 927\n3 3 248\n2 4 834\n3 4 285","125\n0\n15300\n840659991"]],"created_at":"2026-03-03 11:09:25"}}