21 Days Training // Day 19

T0. path

My idea : enum.

Search all possiblities, check if it is valid, find the mininum distance.

Constraints :

Expected : 20/20

Solution : The bitonic tour, DP.

Notice that walking from A to B and then walking from B to A is equal to walking from A to B 2 times in paths with no intersections.

So we use dp[i][j] to record the mininum distance when the 1st path walks to i and the 2nd path walks to j.

The solution above is the standard solution to solve the bitonic tour with the mininum distance.

For the special points given in the problem, add some extra conditions.

Code :

/*
!!! Copy from blog.csdn.net !!!
*/

#include <bits/stdc++.h>
using namespace std;

int main() {
    freopen("path.in", "r", stdin);
    freopen("path.out", "w", stdout);
    int N, u, v;cin >> N >> u >> v;
    pair<int, int> P[N];
    for (int i=0;i<N;i++) {
        int x, y;cin >> x >> y;
        P[i] = make_pair(x, y);
    }
    double dp[N][N];

    for (int i=0;i<N;i++) {
        for (int j=0;j<N;j++) {
            dp[i][j]=1.797e308;
        }
    }
    dp[0][0] = 0;
    for (int i=0;i<N;i++) {
        for (int j=0;j<N;j++) {
            if (i==j&&(i)) continue;
            int k=max(i, j)+1;
            if (k==N) {
                if (i<N-1) {
                    dp[N-1][N-1] = min(dp[N-1][N-1], dp[i][j]+sqrt((P[i].first-P[N-1].first)*(P[i].first-P[N-1].first)+(P[i].second-P[N-1].second)*(P[i].second-P[N-1].second)));
                }
                if (j<N-1) {
                    dp[N-1][N-1] = min(dp[N-1][N-1], dp[i][j]+sqrt((P[j].first-P[N-1].first)*(P[j].first-P[N-1].first)+(P[j].second-P[N-1].second)*(P[j].second-P[N-1].second)));
                }
            }
            else {
                if (k!=u) dp[k][j] = min(dp[k][j], dp[i][j]+sqrt((P[k].first-P[i].first)*(P[k].first-P[i].first)+(P[k].second-P[i].second)*(P[k].second-P[i].second)));
                if (k!=v) dp[i][k] = min(dp[i][k], dp[i][j]+sqrt((P[k].first-P[j].first)*(P[k].first-P[j].first)+(P[k].second-P[j].second)*(P[k].second-P[j].second)));
            }
        }
    }
    printf("%.2lf", dp[N-1][N-1]);
    return 0;
}