Submission #992654

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

const long long inf = (long long) 1e18;

const int N = 1234567;

int p[N];
long long best[N];
pair < long long, pair <int, int> > e[N];

int find_set(int x) {
  if (x != p[x]) {
    p[x] = find_set(p[x]);
  }
  return p[x];
}

int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  for (int i = 0; i < n; i++) {
    best[i] = inf;
  }
  for (int i = 0; i < m; i++) {
    int x, y, z;
    scanf("%d %d %d", &x, &y, &z);
    e[i] = make_pair(z, make_pair(x, y));
    best[x] = min(best[x], z + 1LL);
    best[y] = min(best[y], z + 2LL);
  }
  for (int it = 0; it < 2; it++) {
    for (int i = 0; i < n; i++) {
      if (best[i] + 2 < best[(i + 1) % n]) {
        best[(i + 1) % n] = best[i] + 2;
      }
    }
  }
  for (int i = 0; i < n; i++) {
    e[m + i] = make_pair(best[i], make_pair(i, (i + 1) % n));
  }
  sort(e, e + m + n);
  for (int i = 0; i < n; i++) {
    p[i] = i;
  }
  long long ans = 0;
  for (int i = 0; i < m + n; i++) {
    int x = e[i].second.first;
    int y = e[i].second.second;
    int fx = find_set(x);
    int fy = find_set(y);
    if (fx != fy) {
      ans += e[i].first;
      p[fx] = fy;
    }
  }
  cout << ans << endl;
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:22:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n, &m);
                         ^
./Main.cpp:28:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &x, &y, &z);
                                  ^

Judge Result