結果

問題 No.2955 Pizza Delivery Plan
コンテスト
ユーザー Nguyễn Phúc Gia Nghi
提出日時 2025-01-29 00:54:40
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,699 bytes
コンパイル時間 1,551 ms
コンパイル使用メモリ 163,972 KB
実行使用メモリ 17,232 KB
最終ジャッジ日時 2025-01-29 00:55:53
合計ジャッジ時間 72,134 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 TLE * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define pii pair<double, double>
#define fi first
#define se second
using namespace std;

double ret=1e18;
int n, k, f[20], vis[20], bit[20];
pii points[20];

double distance(pii x, pii y)
{
    return sqrt((x.fi - y.fi)*(x.fi - y.fi) + (x.se - y.se)*(x.se - y.se));
}

double calc()
{
    // for (int i=1; i<=n; i++) cout << f[i] << " "; cout << endl;
    // for (int i=1; i<n; i++) cout << bit[i] << " "; cout << endl; 
    double dist = 0;
    pii curr = points[f[1]];
    dist += distance({0, 0}, curr);
    for (int i=1; i<=n-1; i++)
    {
        if (bit[i]) dist += distance(curr, {0, 0}), dist += distance({0, 0}, points[f[i+1]]), curr = points[f[i+1]];
        else dist += distance(curr, points[f[i+1]]), curr = points[f[i+1]];
    }
    dist += distance(curr, {0, 0});
    // cout << dist << endl; cout << endl;
    return dist;
}

void xuly()
{
    for (int state = 0; state<=(1<<(n-1))-1; state++) 
    {
        int cnt = 1, mx = 0, car = 1, tmp=state;
        for (int i=1; i<n; i++) bit[i] = 0;
        while (tmp)
        {
            bit[cnt] = tmp&1;
            tmp /= 2;
            cnt++;
        }
        cnt = 1;
        for (int i=1; i<=n-1; i++) if (!bit[i]) car++; else mx = max(mx, car), car = 1; mx = max(mx, car);
        if (mx <= k) ret = min(ret, calc());
    }
}

void gen(int cnt)
{
    if (cnt > n)
    {
        xuly();
        return;
    }
    for (int i=1; i<=n; i++) if (!vis[i])
    {
        vis[i] = 1;
        f[cnt] = i;
        gen(cnt+1);
        vis[i] = 0;
    }
}

int main()
{
    cin >> n >> k;
    for (int i=1; i<=n; i++) cin >> points[i].fi >> points[i].se;
    gen(1);
    cout << fixed << setprecision(9) << ret;
}
0