fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4.  
  5. vector<pair<int, int>> g[100005];
  6. int pri[100005];
  7. int dp[100005];
  8. bool visited[100005];
  9.  
  10. void create() {
  11.     pri[1] = 1;
  12.     for (int i = 4; i <= 100000; i += 2)
  13.         pri[i] = 1;
  14.     for (int i = 3; i * i <= 100000; i += 2) {
  15.         if (pri[i]) continue;
  16.         for (int j = i * i; j <= 100000; j += i)
  17.             pri[j] = 1;
  18.     }
  19. }
  20.  
  21. bool dfs(int u, int target) {
  22.     visited[u] = true;
  23.     if (u == target) return true;
  24.     for (auto it : g[u]) {
  25.         int v = it.first;
  26.         int w = it.second;
  27.         if (!visited[v]) {
  28.             dp[v] = min(dp[u], w);
  29.             if (dfs(v, target)) return true;
  30.         }
  31.     }
  32.     return false;
  33. }
  34.  
  35. signed main() {
  36.     int n, m;
  37.     cin >> n >> m;
  38.     create();
  39.     for (int i = 1; i <= m; ++i) {
  40.         int x, y, z;
  41.         cin >> x >> y >> z;
  42.         g[x].push_back({y, z});
  43.         g[y].push_back({x, z});
  44.     }
  45.  
  46.     vector<int> primes = {1};
  47.     for (int i = 2; i <= n; ++i)
  48.         if (pri[i] == 0) primes.push_back(i);
  49.     primes.push_back(1);
  50.  
  51.     set<pair<int, int>> pi;
  52.     for (int i = 0; i < (int)primes.size(); ++i) {
  53.         for (int j = i + 1; j < (int)primes.size(); ++j) {
  54.             int a = primes[i], b = primes[j];
  55.             for (int k = 1; b * k <= n; ++k)
  56.                 if (k % a != 0)
  57.                     pi.insert({min(a, b * k), max(a, b * k)});
  58.             for (int k = 1; a * k <= n; ++k)
  59.                 if (k % b != 0)
  60.                     pi.insert({min(a * k, b), max(a * k, b)});
  61.         }
  62.     }
  63.  
  64.     int sum = 0;
  65.     for (auto it : pi) {
  66.         int u = it.first, v = it.second;
  67.         fill(dp, dp + n + 1, LLONG_MAX);
  68.         fill(visited, visited + n + 1, false);
  69.         dp[v] = LLONG_MAX;
  70.         dfs(v, u);
  71.         sum += dp[u];
  72.     }
  73.  
  74.     cout << fixed << setprecision(2) << (double)sum / pi.size() << '\n';
  75.     return 0;
  76. }
  77.  
Success #stdin #stdout 0.01s 6980KB
comments (?)
stdin
copy 
5 5 
3 4 2 
1 5 3  
2 5 2  
4 1 1 
1 3 5
stdout
copy 
1.62
https://ideone.com/aO2TSf
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!