2020年蓝桥杯国赛C组补给（洛谷P8733）：最短路径问题详解

一、问题理解与建模

这道题目描述了一个直升机驾驶员需要为山区村庄运送物资的场景。我们需要解决的问题可以抽象为：

1. 图论模型：将每个村庄看作图中的一个节点，村庄之间的距离作为边的权重

2. 限制条件：直升机单次飞行距离不能超过D，这意味着如果两个村庄距离超过D，则不能直接相连

3. 路径要求：从总部(村庄1)出发，访问所有村庄至少一次，最后返回总部

这实际上是带有距离限制的旅行商问题(TSP)变种，需要结合图的最短路径算法和动态规划来解决。

二、算法设计思路

1. 预处理阶段

首先，我们需要处理原始的距离数据。因为直升机有最大飞行距离限制，所以：

• 计算所有村庄之间的两两距离

• 如果距离≤D，保留该距离值

• 如果距离>D，设为无穷大(不可达)

2. 可达性检查

使用Floyd-Warshall算法计算所有点对之间的最短路径。这有两个目的：

1. 检查是否所有村庄都可到达(从总部出发，经过若干次加油)

2. 计算实际可飞行的最短路径(可能需要在某些村庄中转加油)

3. 动态规划解决TSP

使用状态压缩动态规划来解决旅行商问题：

• 状态表示：dp[mask][last]表示已访问村庄集合为mask，最后访问的是last村庄时的最短距离

• 状态转移：对于每个状态，尝试从未访问的村庄中选择一个可达的村庄进行转移

• 初始状态：只访问了总部(村庄0)，距离为0

• 最终结果：所有村庄都访问过后(mask为全1)，从最后访问的村庄返回总部的距离总和

三、实现详解

1. 距离计算

double calculateDistance(int x1, int y1, int x2, int y2) {
    return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
}

这个辅助函数简单地计算两点之间的欧几里得距离。

2. 输入处理与初始化

cin >> n >> D;
vector<pair<int, int>> villages(n);
for (int i = 0; i < n; ++i) {
    cin >> villages[i].first >> villages[i].second;
}

读取村庄数量和最大飞行距离，然后存储每个村庄的坐标。

3. 构建邻接矩阵

vector<vector<double>> dist(n, vector<double>(n, INF));
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
        double d = calculateDistance(villages[i].first, villages[i].second, 
                                   villages[j].first, villages[j].second);
        dist[i][j] = (d <= D) ? d : INF;
    }
}

构建邻接矩阵，只保留可达的边(距离≤D)。

4. Floyd-Warshall算法

for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (dist[i][k] + dist[k][j] < dist[i][j]) {
                dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
}

通过中间点k，更新i到j的最短距离，考虑了中转加油的情况。

5. 可达性检查

for (int i = 1; i < n; ++i) {
    if (dist[0][i] == INF || dist[i][0] == INF) {
        cout << "-1" << endl;
        return 0;
    }
}

如果有村庄不可达，直接输出-1。

6. TSP动态规划

vector<vector<double>> dp(1 << n, vector<double>(n, INF));
dp[1][0] = 0; // 初始状态

for (int mask = 1; mask < (1 << n); ++mask) {
    for (int last = 0; last < n; ++last) {
        if (!(mask & (1 << last))) continue;
        if (dp[mask][last] == INF) continue;
        
        for (int next = 0; next < n; ++next) {
            if (mask & (1 << next)) continue;
            int new_mask = mask | (1 << next);
            if (dist[last][next] + dp[mask][last] < dp[new_mask][next]) {
                dp[new_mask][next] = dist[last][next] + dp[mask][last];
            }
        }
    }
}

这是TSP问题的核心解法，使用状态压缩动态规划来寻找最短路径。

7. 结果计算

double min_dist = INF;
int full_mask = (1 << n) - 1;
for (int last = 1; last < n; ++last) {
    if (dp[full_mask][last] + dist[last][0] < min_dist) {
        min_dist = dp[full_mask][last] + dist[last][0];
    }
}

在所有村庄都访问过后，加上从最后访问的村庄返回总部的距离，取最小值。

四、完整代码

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespACe std;

const double INF = 1e18;

// 计算两点之间的欧几里得距离
double calculateDistance(int x1, int y1, int x2, int y2) {
    return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
}

int main() {
    int n, D;
    cin >> n >> D;
    
    vector<pair<int, int>> villages(n);
    for (int i = 0; i < n; ++i) {
        cin >> villages[i].first >> villages[i].second;
    }
    
    // 构建邻接矩阵，计算所有村庄之间的距离
    vector<vector<double>> dist(n, vector<double>(n, INF));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            double d = calculateDistance(villages[i].first, villages[i].second, 
                                       villages[j].first, villages[j].second);
            // 如果距离超过D，则不能直接到达
            dist[i][j] = (d <= D) ? d : INF;
        }
    }
    
    // Floyd-Warshall算法计算所有点对之间的最短路径
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    
    // 检查是否所有村庄都可到达
    for (int i = 1; i < n; ++i) {
        if (dist[0][i] == INF || dist[i][0] == INF) {
            cout << "-1" << endl;
            return 0;
        }
    }
    
    // 旅行商问题(TSP)的动态规划解法
    vector<vector<double>> dp(1 << n, vector<double>(n, INF));
    dp[1][0] = 0; // 初始状态：只访问了总部(村庄0)
    
    for (int mask = 1; mask < (1 << n); ++mask) {
        for (int last = 0; last < n; ++last) {
            if (!(mask & (1 << last))) continue;
            if (dp[mask][last] == INF) continue;
            
            for (int next = 0; next < n; ++next) {
                if (mask & (1 << next)) continue;
                int new_mask = mask | (1 << next);
                if (dist[last][next] + dp[mask][last] < dp[new_mask][next]) {
                    dp[new_mask][next] = dist[last][next] + dp[mask][last];
                }
            }
        }
    }
    
    // 计算最终结果：访问所有村庄后返回总部
    double min_dist = INF;
    int full_mask = (1 << n) - 1;
    for (int last = 1; last < n; ++last) {
        if (dp[full_mask][last] + dist[last][0] < min_dist) {
            min_dist = dp[full_mask][last] + dist[last][0];
        }
    }
    
    cout << fixed << setprecision(2) << min_dist << endl;
    return 0;
}

总结

这道题目综合考察了图论算法和动态规划的应用。通过将实际问题抽象为图论模型，然后结合Floyd-Warshall算法和状态压缩动态规划，我们能够有效地解决这个带有约束条件的路径规划问题。理解这种解题思路对于解决类似的组合优化问题非常有帮助。