{"problem":{"name":"[DTCPC 2024] 环","description":{"content":"给定无重边无自环的有向图 $G$ 和序列 $\\{a_n\\}$，每次可以花费 $a_i+a_j$ 的代价加上一条 $i\\to j$ 的边，试花费最小代价使得可以找到 $k\\geq 2$ 个不同的点 $p_1,p_2,\\dots,p_k$，满足 $\\forall i\\in [1,k]$，都有一条 $p_i\\to p_{i\\bmod k+1}$ 的边。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10166"},"statements":[{"statement_type":"Markdown","content":"给定无重边无自环的有向图 $G$ 和序列 $\\{a_n\\}$，每次可以花费 $a_i+a_j$ 的代价加上一条 $i\\to j$ 的边，试花费最小代价使得可以找到 $k\\geq 2$ 个不同的点 $p_1,p_2,\\dots,p_k$，满足 $\\forall i\\in [1,k]$，都有一条 $p_i\\to p_{i\\bmod k+1}$ 的边。\n\n## Input\n\n第一行两个整数 $n,m$（$2\\le n\\le 5 \\times 10^5$，$n-1 \\le m \\le 10^6$），表示图的点数和边数。\n\n第二行输入 $n$ 个整数，表示序列 $\\{a_n\\}$（$1\\le a_i\\le 10^9$）。\n\n接下来 $m$ 行，每行两个整数 $u,v$（$1\\le u,v\\le n$），表示存在一条有向边 $u\\to v$。\n\n## Output\n\n一行一个整数表示最小代价。\n\n[samples]\n\n## Background\n\n环","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10166","tags":["贪心","2024","拓扑排序","洛谷月赛"],"sample_group":[["5 5\n1 2 3 4 5 \n1 2\n2 3\n3 4\n1 5\n5 4 ","3"]],"created_at":"2026-03-03 11:09:25"}}