题解 | 无人机物流网络最优路径规划

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;

// 定义图的邻接表结构
vector<vector<pair<int, int>>> graph;
vector<int> dist;  // 存储从起点到各点的最短距离
vector<vector<int>> prevNodes;  // 存储最短路径的前驱节点

void dijkstra(int start, int n) {
    // 初始化距离数组，初始值为无穷大
    dist.assign(n + 1, INT_MAX);
    // 初始化前驱节点数组
    prevNodes.assign(n + 1, vector<int>());
    
    // 使用优先队列（最小堆）来存储待处理的节点
    // pair的第一个元素是距离，第二个元素是节点编号
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    
    // 起点到自己的距离为0
    dist[start] = 0;
    pq.push({0, start});
    
    while (!pq.empty()) {
        // 取出当前距离最小的节点
        int currentDist = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        
        // 如果当前距离不是最短距离，跳过（因为可能已经更新过）
        if (currentDist > dist[u]) continue;
        
        // 遍历当前节点的所有邻居
        for (auto& neighbor : graph[u]) {
            int v = neighbor.first;
            int weight = neighbor.second;
            
            // 计算通过当前节点到达邻居的新距离
            int newDist = dist[u] + weight;
            
            // 如果找到更短的路径
            if (newDist < dist[v]) {
                dist[v] = newDist;
                // 清空前驱节点，因为找到了更短的路径
                prevNodes[v].clear();
                prevNodes[v].push_back(u);
                pq.push({newDist, v});
            }
            // 如果找到相同长度的路径，添加前驱节点
            else if (newDist == dist[v]) {
                prevNodes[v].push_back(u);
            }
        }
    }
}

// 使用BFS收集所有可能的下一跳节点
void collectNextHops(int start, int end, vector<int> &nextHops) {
    // 如果起点就是终点，没有下一跳
    if (start == end) return;
    
    // 使用队列进行BFS遍历
    queue<int> q;
    q.push(end);
    
    // 使用集合记录已访问的节点，避免重复处理
    vector<bool> visited(graph.size(), false);
    visited[end] = true;
    
    while (!q.empty()) {
        int current = q.front();
        q.pop();
        
        // 遍历当前节点的所有前驱节点
        for (int prev : prevNodes[current]) {
            // 如果前驱节点是起点，那么当前节点就是可能的下一跳
            if (prev == start) {
                nextHops.push_back(current);
            }
            // 如果前驱节点未被访问，加入队列继续搜索
            else if (!visited[prev]) {
                visited[prev] = true;
                q.push(prev);
            }
        }
    }
}

int main() {
    int N, K;
    cin >> N >> K;
    
    // 初始化图结构，大小为N+1（节点编号从1到N）
    graph.resize(N + 1);
    
    // 读取所有边信息并构建图
    for (int i = 0; i < K; i++) {
        int u, v, e;
        cin >> u >> v >> e;
        // 添加双向边（无向图）
        graph[u].push_back({v, e});
        graph[v].push_back({u, e});
    }
    
    int start, end;
    cin >> start >> end;
    
    // 特殊情况：起点和终点相同
    if (start == end) {
        cout << 0 << endl;
        cout << -1 << endl;
        return 0;
    }
    
    // 执行Dijkstra算法计算最短路径
    dijkstra(start, N);
    
    // 如果终点不可达
    if (dist[end] == INT_MAX) {
        cout << -1 << endl;
        cout << -1 << endl;
        return 0;
    }
    
    // 输出最低总能耗
    cout << dist[end] << endl;
    
    // 收集所有可能的下一跳节点
    vector<int> nextHops;
    collectNextHops(start, end, nextHops);
    
    // 如果没有找到下一跳（理论上不应该发生，除非图结构有问题）
    if (nextHops.empty()) {
        cout << -1 << endl;
    } else {
        // 对下一跳节点进行排序
        sort(nextHops.begin(), nextHops.end());
        // 输出所有下一跳节点
        for (int i = 0; i < nextHops.size(); i++) {
            if (i > 0) cout << " ";
            cout << nextHops[i];
        }
        cout << endl;
    }
    
    return 0;
}