fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define M 1000000007
  4. #define F first
  5. #define S second
  6. #define mp make_pair
  7. #define pb push_back
  8. #define gcd __gcd
  9. #define pr(n) printf("%d ",n)
  10. #define out(n) printf("%d\n",n)
  11. #define inl(a) cin >> a
  12. #define prl(a) cout << a << " "
  13. #define outl(a) cout << a << endl
  14. #define yes printf("YES\n")
  15. #define no printf("NO\n")
  16. #define lin printf("\n")
  17. #define dbg(v,i,n) for(i=0;i<n;i++)pr(v[i]); lin
  18. #define ck printf("continue\n")
  19. #define all(vec) vec.begin(),vec.end()
  20. #define asc(vec) sort(vec.begin(),vec.end())
  21. #define lower(v,k) lower_bound(v.begin(),v.end(),k)-v.begin()
  22. #define upper(v,k) upper_bound(v.begin(),v.end(),k)-v.begin()
  23. #define tf(mytuple) get<0>(mytuple)
  24. #define ts(mytuple) get<1>(mytuple)
  25. #define tt(mytuple) get<2>(mytuple)
  26. #define ii pair<int,int>
  27. #define vi vector<int>
  28. #define vii vector<pair<int,int> >
  29. #define vvi vector<vector<int> >
  30. #define viii vector<pair<pair<int,int>,int> >
  31. #define vvii vector<vector<pair<int,int> > >
  32. #define lp(i,a,b) for(i=a;i<b;i++)
  33. #define rep(i,n) for(i=0;i<n;i++)
  34. #define N 5000001
  35. typedef long long int ll;
  36.  
  37. class MahdiJumping {
  38. public:
  39. 	long long minDis(int, int, int, int, int);
  40. };
  41.  
  42. long long minDis(int n, int A, int B, int a, int b)
  43. {
  44.     ll ans=N;
  45.     ans*=N;
  46.     vector<ll> dp(n,ans);
  47.     //vi vis(n,0);
  48.     vector<bool> vis(n,false);
  49.     dp[0]=0;
  50.     priority_queue<pair<ll,int>,vector<pair<ll,int> > ,greater<pair<ll,int> > > pq;
  51.     pq.push({0,0});
  52.     pair<ll,int> xy;
  53.     int s;
  54.     while(!pq.empty() && !vis[n-1])
  55.     {
  56.         xy=pq.top();
  57.         pq.pop();
  58.         s=xy.S,ans=xy.F;
  59.         if(!vis[s])
  60.         {
  61.             vis[s]=1;
  62.             if(s+1<n && !vis[s+1] && dp[s+1]>dp[s]+a)
  63.                 dp[s+1]=dp[s]+a,pq.push({dp[s+1],s+1});
  64.             ans=A,ans*=s,ans+=B;
  65.             ans%=n;
  66.             if(!vis[ans] && dp[ans]>dp[s]+b)
  67.                 dp[ans]=dp[s]+b,pq.push({dp[ans],ans});
  68.         }
  69.     }
  70.     return dp[n-1];
  71. }
  72.  
  73. int main()
  74. {
  75. 	outl(minDis(5000000, 1, 5, 1, 5000000));
  76. }
  77. //Powered by [KawigiEdit] 2.0!
Success #stdin #stdout 0.7s 173920KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4999999
https://ideone.com/78xQto
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!