题目详情题解（0）讨论（0）提交记录（0）

AT_abc210_e.[ABC210E] Ring MST

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

  • 给定一张 nn 个点的图，顶点的编号为 [0,n−1][0, n - 1]，同时给出两个长度为 mm 的数组 a1,a2,⋯ ,ama_1, a_2, \cdots, a_m 和 b1,b2,⋯ ,bmb_1, b_2, \cdots, b_m。

  • 初始时图中并没有任何边，你可以按照以下操作加边：选择一个 1≤i≤m1 \le i \le m 和一个 0≤x<n0 \le x < n，并在顶点 xx 和顶点 (x+ai) mod n(x + a_i) \bmod n 中添加一条长度为 bib_i 的边。

  • 你现在想要知道，你添加的边的长度总和至少为多少，才能使得整个图连通?如果无论如何都不能使整个图连通，输出 -1。

输入格式

  • 第一行包含两个整数 n,mn, m，分别表示图的顶点个数和数组的数组的长度。

  • 接下来 mm 行，第 ii 行包含两个整数 ai,bi (1≤ai≤n−1)a_i, b_i\space(1 \le a_i \le n - 1)。

输出格式

  • 输出一个数，表示答案。

输入输出样例

  • 输入#1

    4 2
2 3
3 5

    输出#1

    11

  • 输入#2

    6 1
3 4

    输出#2

    -1

说明/提示

  • 对于 30%30 \% 的数据：1≤n,m≤1000,1≤bi≤1091 \le n, m \le 1000, 1 \le b_i \le 10^9。

  • 对于 60%60 \% 的数据：1≤n,m≤105,1≤bi≤1091 \le n, m \le 10^5, 1 \le b_i \le 10^9。

  • 对于 100%100 \% 的数据：1≤n≤109,1≤m≤105,1≤bi≤1091 \le n \le 10^9, 1 \le m \le 10^5, 1 \le b_i \le 10^9。

翻译提供者：Sunrize。

输入解题思路，AI测评打分。不知道怎么写?

首页