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.     vector<int> vis(n,0);
  48.     dp[0]=0;
  49.     priority_queue<pair<ll,int>,vector<pair<ll,int> > ,greater<pair<ll,int> > > pq;
  50.     pq.push({0,0});
  51.     pair<ll,int> xy;
  52.     int s;
  53.     while(!pq.empty() && !vis[n-1])
  54.     {
  55.         xy=pq.top();
  56.         pq.pop();
  57.         s=xy.S,ans=xy.F;
  58.         if(!vis[s])
  59.         {
  60.             vis[s]=1;
  61.             if(s+1<n && !vis[s+1] && dp[s+1]>dp[s]+a)
  62.                 dp[s+1]=dp[s]+a,pq.push({dp[s+1],s+1});
  63.             ans=A,ans*=s,ans+=B;
  64.             ans%=n;
  65.             if(!vis[ans] && dp[ans]>dp[s]+b)
  66.                 dp[ans]=dp[s]+b,pq.push({dp[ans],ans});
  67.         }
  68.     }
  69.     return dp[n-1];
  70. }
  71.  
  72. int main()
  73. {
  74. 	outl(minDis(5000000, 1, 5, 1, 5000000));
  75. }
  76. //Powered by [KawigiEdit] 2.0!
Success #stdin #stdout 0.69s 192920KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4999999
https://ideone.com/VeXNVJ
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!