90pts 不知道其中一种写法为啥能过另一种不行
查看原帖
90pts 不知道其中一种写法为啥能过另一种不行
817442
Sakuya_maid楼主2024/12/16 19:58

这是不能过的：

#include <bits/stdc++.h>

using namespace std;
typedef unsigned long long ULL;
using LL = long long;

mt19937_64 rd(time(0));
constexpr int N = 3e5 + 5, mod = 998244353;
constexpr double eps = 1e-8;
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")

#define fi first
#define se second
#define int long long
#define lowbit(x) (x & (-x))
#define PII pair<int, int>
#define mid ((l + r) >> 1)

// int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int ksm(int a, int b){
    a %= mod;
    int res = 1;
    while(b){
        if(b & 1)res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int n, m;

double g[22][22];
double lim;

double x[N], y[N];

void Sakuya()
{
    cin >> n >> lim;

    for(int i = 1; i <= n; ++ i){
        cin >> x[i] >> y[i];
    }

    auto get = [&](int id1, int id2) -> double {
        return sqrt((x[id1] - x[id2]) * (x[id1] - x[id2]) + (y[id1] - y[id2]) * (y[id1] - y[id2]));
    };

    for(int i = 1; i <= n; ++ i){
        for(int j = 1; j <= n; ++ j){
            g[i][j] = get(i, j);
        }
    }

    for(int k = 1; k <= n; ++ k){
        for(int i = 1; i <= n; ++ i){
            for(int j = 1; j <= n; ++ j){
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }

    for(int i = 1; i <= n; ++ i){
        for(int j = 1; j <= n; ++ j){
            if(g[i][j] > lim)g[i][j] = 1e18;
        }
    }

    vector dp(1 << n, vector<double>(n + 1, 1e18));

    dp[1 << (1 - 1)][1] = 0;
    
    for(int S = 0; S < (1 << n); ++ S){
        for(int i = 1; i <= n; ++ i){
            if(!((S >> (i - 1)) & 1))continue;
            for(int j = 1; j <= n; ++ j){
                if(!((S >> (j - 1)) & 1))continue;
                dp[S][i] = min(dp[S][i], dp[S ^ (1 << (i - 1))][j] + g[j][i]);
            }
        }
    }

    double ans = 1e18;
    int U = (1 << n) - 1;
    for(int i = 2; i <= n; ++ i){
        ans = min(ans, dp[U][i] + g[i][1]);
        ans = min(ans, 2 * dp[U][i]);
    }

    cout << fixed << setprecision(2) << ans << "\n";
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // int T;
    // for (cin >> T; T -- ; )
        Sakuya();

}

这是能过得：

#include <bits/stdc++.h>

using namespace std;
typedef unsigned long long ULL;
using LL = long long;

mt19937_64 rd(time(0));
constexpr int N = 3e5 + 5, mod = 998244353;
constexpr double eps = 1e-8;
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")

#define fi first
#define se second
#define int long long
#define lowbit(x) (x & (-x))
#define PII pair<int, int>
#define mid ((l + r) >> 1)

// int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int ksm(int a, int b){
    a %= mod;
    int res = 1;
    while(b){
        if(b & 1)res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int n, m;

double g[22][22];
double lim;

double x[N], y[N];

void Sakuya()
{
    cin >> n >> lim;

    for(int i = 1; i <= n; ++ i){
        cin >> x[i] >> y[i];
    }

    auto get = [&](int id1, int id2) -> double {
        return sqrt((x[id1] - x[id2]) * (x[id1] - x[id2]) + (y[id1] - y[id2]) * (y[id1] - y[id2]));
    };

    for(int i = 1; i <= n; ++ i){
        for(int j = 1; j <= n; ++ j){
            g[i][j] = get(i, j);
        }
    }

    for(int i = 1; i <= n; ++ i){
        for(int j = 1; j <= n; ++ j){
            if(g[i][j] > lim)g[i][j] = 1e18;
        }
    }


    for(int k = 1; k <= n; ++ k){
        for(int i = 1; i <= n; ++ i){
            for(int j = 1; j <= n; ++ j){
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }

    vector dp(1 << n, vector<double>(n + 1, 1e18));

    dp[1 << (1 - 1)][1] = 0;
    
    for(int S = 0; S < (1 << n); ++ S){
        for(int i = 1; i <= n; ++ i){
            if(!((S >> (i - 1)) & 1))continue;
            for(int j = 1; j <= n; ++ j){
                if(!((S >> (j - 1)) & 1))continue;
                dp[S][i] = min(dp[S][i], dp[S ^ (1 << (i - 1))][j] + g[j][i]);
            }
        }
    }

    double ans = 1e18;
    int U = (1 << n) - 1;
    for(int i = 2; i <= n; ++ i){
        ans = min(ans, dp[U][i] + g[i][1]);
        ans = min(ans, 2 * dp[U][i]);
    }

    cout << fixed << setprecision(2) << ans << "\n";
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // int T;
    // for (cin >> T; T -- ; )
        Sakuya();

}

然后奇怪得一件事情就是 我不给不满足条件的赋值1e18 变成 我中间和最后转移得时候多加一个条件判断能不能转移也是90pts 第四个点一直wa

2024/12/16 19:58