結果

問題 No.2955 Pizza Delivery Plan
コンテスト
ユーザー Nguyễn Phúc Gia Nghi
提出日時 2025-01-29 21:45:57
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 147 ms / 2,000 ms
コード長 1,459 bytes
コンパイル時間 1,532 ms
コンパイル使用メモリ 163,680 KB
実行使用メモリ 106,308 KB
最終ジャッジ日時 2025-01-29 21:46:03
合計ジャッジ時間 6,094 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

int n, k;
pii points[20];
double dist[20][20], dp[1<<15][20][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));
}

int main()
{
    cin >> n >> k;
    for (int i=1; i<=n; i++) cin >> points[i].fi >> points[i].se;
    points[++n] = {0.0, 0.0}; // diem bat dau

    for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) if (i != j)
        dist[i][j] = distance(points[i], points[j]);
    for (int state = 0; state <= (1<<(n-1))-1; state++)
        for (int i=0; i<=n; i++)
            for (int j=0; j<=k; j++) dp[state][i][j] = 1e18;
    dp[0][n][k] = 0;

    for (int state = 0; state <= (1<<(n-1))-1; state++)
        for (int from = 1; from <= n; from++) if ((from == n) || ((state >> (from-1)) & 1))
        {
            for (int remain = 1; remain <= k; remain++)
                for (int to = 1; to <= n; to++) if ((~state >> (to-1)) & 1)
                    dp[state | (1<<(to-1))][to][remain-1] = min(dp[state | (1<<(to-1))][to][remain-1], 
                                                                dp[state][from][remain] + dist[from][to]);
            for (int remain = 0; remain <= k; remain++) 
                dp[state][n][k] = min(dp[state][n][k], dp[state][from][remain] + dist[from][n]);
        }
    cout << fixed << setprecision(9) << dp[(1<<(n-1))-1][n][k];
}
0