T30:补给

1）题目意思

有 n 个村庄（1 号是总部），每个村庄坐标已知。直升机每次飞行的距离不能超过 D，但每到一个村庄都能加满油（所以每一段航程只要不超过 D 就合法）。

小蓝每个月从 1 号出发，要访问所有村庄至少一次（可以重复经过某些村庄，包括总部），最后回到 1 号。问最少总飞行距离是多少，输出保留 2 位小数。

---

2）思路解析（最短路预处理 + TSP 状压 DP）

关键观察 1：允许中途经过其它村庄/总部加油

从村 i 到村 j 不一定能直飞（距离可能 > D），但可以通过中转若干次。只要每一段不超过 D 就行。

因此我们先把图建成：

• 如果 dist(i,j) <= D，就有一条边，权重是欧氏距离

然后对这个图做 所有点对最短路（因为中转可能更短/更可行）：

• 得到 g[i][j]：从 i 到 j 的最小可行飞行距离
• 如果 i 到 j 不可达，则 g[i][j]=INF

若有任意一个点从总部不可达，那么一定无法完成任务，输出 -1（题目没写这种情况，但数据可能保证可行；这里写上更稳）。

关键观察 2：访问所有点并回到起点 = TSP（可重复经过点，但最短路已吸收重复）

因为我们把“中转”都折算进 g[i][j] 里，所以路线只需要在 g 上做：

• 从 1 出发，访问每个点至少一次，回到 1

在最短路度量下，最优解等价于“每个点访问一次”的 TSP 状压 DP。

状态定义

用 mask 表示已访问集合（0..n-1 对应村 1..n）：

• dp[mask][i]：从 0（总部）出发，访问了 mask 中的点，最后停在 i 的最小距离

初始化：

• dp[1<<0][0]=0

转移：

• dp[mask|(1<<j)][j] = min(dp[mask|(1<<j)][j], dp[mask][i] + g[i][j])

答案：

• min_i dp[ALL][i] + g[i][0]

复杂度：

• Floyd：O(n^3)，n<=20 很小
• TSP：O(n^2 * 2^n)，n<=20 可过

---

3）代码

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

const double INF = 1e100;                                   // 定义一个很大的数表示不可达

static double x[25], y[25];                                  // 存坐标
static double g[25][25];                                     // g[i][j]：可行飞行图上的最短路
static double dp[1<<20][20];                                 // TSP dp数组（n<=20）

int main(){                                                  // 主函数入口
    ios::sync_with_stdio(false);                             // 加速输入输出
    cin.tie(nullptr);                                        // 加速输入输出

    int n;                                                   // 村庄数量
    double D;                                                // 单次最大飞行距离
    cin >> n >> D;                                           // 读入n和D

    for(int i=0;i<n;i++){                                    // 读入每个村坐标
        cin >> x[i] >> y[i];                                 // 第i个村的坐标
    }

    for(int i=0;i<n;i++){                                    // 初始化g为INF
        for(int j=0;j<n;j++){                                // 初始化g为INF
            g[i][j]=INF;                                     // 先设不可达
        }
        g[i][i]=0.0;                                         // 自己到自己距离为0
    }

    for(int i=0;i<n;i++){                                    // 建图：能直飞就连边
        for(int j=0;j<n;j++){                                // 建图：能直飞就连边
            double dx=x[i]-x[j];                             // x差
            double dy=y[i]-y[j];                             // y差
            double d=sqrt(dx*dx+dy*dy);                      // 欧氏距离
            if(d<=D+1e-12) g[i][j]=min(g[i][j],d);           // 若可直飞，则更新边权
        }
    }

    for(int k=0;k<n;k++){                                    // Floyd求全源最短路
        for(int i=0;i<n;i++){                                // Floyd求全源最短路
            for(int j=0;j<n;j++){                            // Floyd求全源最短路
                if(g[i][k]+g[k][j]<g[i][j]){                 // 若经过k更短
                    g[i][j]=g[i][k]+g[k][j];                 // 更新最短路
                }
            }
        }
    }

    for(int i=0;i<n;i++){                                    // 检查是否所有点与总部连通
        if(g[0][i]>=INF/2){                                  // 如果总部到i不可达
            cout << -1 << endl;                              // 输出-1
            return 0;                                        // 结束程序
        }
    }

    int ALL=(1<<n)-1;                                        // ALL表示访问所有点

    for(int mask=0;mask<=ALL;mask++){                        // 初始化dp为INF
        for(int i=0;i<n;i++){                                // 初始化dp为INF
            dp[mask][i]=INF;                                 // 设为不可达
        }
    }

    dp[1<<0][0]=0.0;                                         // 初始：只在总部，代价0

    for(int mask=0;mask<=ALL;mask++){                        // 枚举所有mask
        for(int i=0;i<n;i++){                                // 枚举当前停在i
            if(!(mask&(1<<i))) continue;                     // i必须在mask中
            double cur=dp[mask][i];                          // 取当前最短距离
            if(cur>=INF/2) continue;                         // 不可达跳过

            for(int j=0;j<n;j++){                            // 枚举下一步去j
                if(mask&(1<<j)) continue;                    // 已访问过则跳过
                int nmask=mask|(1<<j);                       // 新mask
                double nxt=cur+g[i][j];                      // 新距离
                if(nxt<dp[nmask][j]) dp[nmask][j]=nxt;       // 更新dp
            }
        }
    }

    double ans=INF;                                          // 最终答案
    for(int i=0;i<n;i++){                                    // 枚举最后停在i
        ans=min(ans,dp[ALL][i]+g[i][0]);                     // 回到总部，取最小
    }

    cout.setf(ios::fixed);                                   // 固定小数输出
    cout << setprecision(2) << ans << endl;                  // 输出保留2位小数
    return 0;                                                // 程序结束
}