fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #include <iostream>
  4. #define Sa7afy_H333 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  5. #define Time cerr << "Time Taken: " << (float)clock() / CLOCKS_PER_SEC << " Secs" << "\n";
  6. #define cin(v) for (auto&i:v) cin >> i;
  7. #define cout(v) for (auto&i:v) cout << i << " ";cout<<e;
  8. #include <algorithm>
  9. #include <vector>
  10. #define ll long long int
  11. #define e '\n'
  12. #define PI acos(-1)
  13. #define PHI (long double)1.61803398875 //golden ratio
  14. #define sin(a) sin((a)*PI/180)
  15. #define cos(a) cos((a)*PI/180)
  16. #define tan(a) tan((a)*PI/180)
  17. #define  eb emplace_back
  18. #define ones(x) __builtin_popcountll(x)
  19. #define all(v) v.begin(), v.end()
  20. #define allr(v) v.rbegin(), v.rend()
  21. #define pii pair<ll,ll>
  22. #define vi vector<int>
  23. #define vll vector<ll>
  24. using std::cout;
  25. using std::array; using std::fill;
  26. using std::fill_n;
  27. #include <set>
  28. #include <deque>
  29. #define d2v vector<vector<int>>
  30. typedef pair<int,int> Pii;
  31. #define  pb push_back
  32.  
  33. const int mod = 1e9+7;
  34. ll mult(ll a, ll b){ return ((a % mod) * (b % mod)) % mod; }
  35. ll add(ll a, ll b) { return ((a % mod) + (b % mod)) % mod; }
  36. ll sub(ll a, ll b) { return ((a % mod) - (b % mod) + mod) % mod; }
  37.  
  38. const int N = 4e5+10;
  39. const int N2=2e5+10;
  40. const ll INF = 1e18;
  41. vector<pair<int, int>> adj[N2];
  42. vector<int>spf(N+1);
  43. vector<int> pr;
  44.  
  45. void build() {
  46.     for (int i = 2; i <= N; ++i) {
  47.         if (spf[i] == 0) {
  48.             spf[i] = i;
  49.             pr.push_back(i);
  50.         }
  51.         for (int j = 0; i * pr[j] <= N; ++j) {
  52.             spf[i * pr[j]] = pr[j];
  53.             if (pr[j] == spf[i]) {
  54.                 break;
  55.             }
  56.         }
  57.     }
  58. }
  59.  
  60. ll pw (ll n,ll ex) {
  61.     if (ex == 0)return 1;
  62.     ll res = pw(n, ex / 2);
  63.     res = (res*res);
  64.     if (ex & 1) {
  65.         res = (res * n);
  66.     }
  67.     return res ;
  68. }
  69.  
  70. ll divsum(ll n) {
  71.     map<int, int> facts;
  72.     while (n > 1) {
  73.         int p = spf[n];
  74.         facts[p]++;
  75.         n /= p;
  76.     }
  77.     ll ans = 1;
  78.     for (auto x: facts)
  79.         ans *= (pw(x.first, x.second + 1) - 1) / (x.first - 1);
  80.     return ans;
  81. }
  82.  
  83.  
  84. void solve() {
  85.     ll n, m, x, y, s, f;
  86.     cin >> n >> m >> s >> f;
  87.     for (int i = 0; i < m; i++) {
  88.         cin >> x >> y;
  89.         adj[x].eb(y, 0);
  90.         adj[y].eb(x, divsum(x + y));
  91.     }
  92.     vector<ll> dis(n + 1, INF);
  93.     dis[s] = 0;
  94.     priority_queue<pii, vector<pii >, greater<pii>> q;
  95.     q.push({0, s});
  96.     while (!q.empty()) {
  97.         int v = q.top().second;
  98.         int d_v = q.top().first;
  99.         q.pop();
  100.         for (auto ed: adj[v]) {
  101.             int to = ed.first, len = ed.second;
  102.             if (dis[v] + len < dis[to]) {
  103.                 dis[to] = dis[v] + len;
  104.                 q.push({dis[to], to});
  105.             }
  106.         }
  107.     }
  108.     if (dis[f] == INF) {
  109.         cout << -1 << e;
  110.     } else cout << dis[f] << e;
  111. }
  112.  
  113.  
  114. signed main() {
  115.     build();
  116.     Sa7afy_H333
  117.     int tests = 1;
  118.     //cin >> tests;
  119.     for (int i = 1; i <= tests; i++) {
  120.         /*cout<<"Case #"<<i<<": ";*/
  121.         solve();
  122.     }
  123.     Time
  124. }
  125.  
Success #stdin #stdout #stderr 0.01s 9820KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
stderr
copy 
Time Taken: 0.013235 Secs
https://ideone.com/1jIdpI
language:
C++ (gcc 8.3)
created:
12 hours 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!