fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const long long MaxN = 2e3 + 5;
  4. long long n;
  5. double x[MaxN], y[MaxN],dp[MaxN][MaxN];
  6.  
  7. int main()
  8. {
  9.     ios_base::sync_with_stdio(0);
  10.     cin.tie(0);
  11.     cin >> n;
  12.     for (long long i=1; i<=n; i++)
  13.     {
  14.         cin >> x[i] >> y[i];
  15.     }
  16.     for (long long i=1; i<=n; i++)
  17.     {
  18.        for (long long j=1; j<=n; j++)
  19.        {
  20.            dp[i][j]=1e18;
  21.        }
  22.     }
  23.     dp[1][1]=0;
  24.     for (long long i=1; i<=n; i++)
  25.     {
  26.         for (long long j=1; j<=i; j++)
  27.         {
  28.             dp[i+1][j]=min(dp[i+1][j],dp[i][j]+sqrt((x[i]-x[i+1])*(x[i]-x[i+1])+(y[i]-y[i+1])*(y[i]-y[i+1])));
  29.             dp[i+1][i]=min(dp[i+1][i],dp[i][j]+sqrt((x[j]-x[i+1])*(x[j]-x[i+1])+(y[j]-y[i+1])*(y[j]-y[i+1])));
  30.         }
  31.     }
  32.     double ans = 4e18;
  33.     for (long long i=1; i<=n; i++)
  34.     {
  35.         ans=min(ans,dp[n][i]);
  36.     }
  37.     cout << fixed <<  setprecision(10) << ans;
  38. }
  39.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4000000000000000000.0000000000
https://ideone.com/S9q9Ib
language:
C++14 (gcc 8.3)
created:
3 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!