1
#include <iostream>
2
#include <vector>
3
#include <limits>
4
#include <tuple>
5
#include <cstdlib>
6
#include <chrono>
7
#include <algorithm> // 用于 make_heap, push_heap, pop_heap
8
#include <unordered_map>
9

10
using namespace std;
11

12
// 定义一个常量表示无穷大
13
const int INF = numeric_limits<int>::max();
14

15
// 定义一个结构体表示图中的边
16
struct Edge {
17
    int to;     // 目标节点
18
    int cost;   // 边的代价
19
};
20

21
// 自定义二叉堆
22
class BinaryHeap {
23
public:
24
    using Element = tuple<int, int, int>; // (当前代价, 当前层, 当前节点)
25

26
    // 插入元素
27
    void push(const Element& element) {
28
        heap.push_back(element);
29
        push_heap(heap.begin(), heap.end(), compare);
30
    }
31

32
    // 弹出最小元素
33
    void pop() {
34
        pop_heap(heap.begin(), heap.end(), compare);
35
        heap.pop_back();
36
    }
37

38
    // 获取最小元素
39
    Element top() const {
40
        return heap.front();
41
    }
42

43
    // 判断堆是否为空
44
    bool empty() const {
45
        return heap.empty();
46
    }
47

48
private:
49
    vector<Element> heap;
50

51
    // 比较函数，用于实现最小堆
52
    static bool compare(const Element& a, const Element& b) {
53
        return get<0>(a) > get<0>(b); // 按代价升序排列
54
    }
55
};
56

57
// 修改后的 Dijkstra 算法
58
using InterLayerConnections = vector<unordered_map<int, vector<pair<int, int>>>>;
59

60
void dijkstra(int startLayer, int startNode, const vector<vector<vector<Edge>>>& graph,
61
    const InterLayerConnections& interLayerCost, vector<vector<int>>& minCost) {
62
    int layers = graph.size();
63
    int nodes = graph[0].size();
64

65
    // 自定义二叉堆，存储 (当前代价, 当前层, 当前节点)
66
    BinaryHeap pq;
67

68
    // 初始化最小代价数组
69
    for (int i = 0; i < layers; ++i) {
70
        fill(minCost[i].begin(), minCost[i].end(), INF);
71
    }
72

73
    // 将起始节点加入队列
74
    minCost[startLayer][startNode] = 0;
75
    pq.push({ 0, startLayer, startNode });
76

77
    // Dijkstra 主循环
78
    while (!pq.empty()) {
79
        auto [currentCost, currentLayer, currentNode] = pq.top();
80
        pq.pop();
81

82
        // 如果当前代价大于已记录的最小代价，跳过
83
        if (currentCost > minCost[currentLayer][currentNode]) continue;
84

85
        // 遍历当前层的邻接节点
86
        for (const auto& edge : graph[currentLayer][currentNode]) {
87
            int nextNode = edge.to;
88
            int nextCost = currentCost + edge.cost;
89

90
            if (nextCost < minCost[currentLayer][nextNode]) {
91
                minCost[currentLayer][nextNode] = nextCost;
92
                pq.push({ nextCost, currentLayer, nextNode });
93
            }
94
        }
95

96
        // 遍历层间连接
97
        if (interLayerCost[currentLayer].count(currentNode)) {
98
            for (const auto& [nextLayer, cost] : interLayerCost[currentLayer].at(currentNode)) {
99
                int nextCost = currentCost + cost;
100
                if (nextCost < minCost[nextLayer][currentNode]) {
101
                    minCost[nextLayer][currentNode] = nextCost;
102
                    pq.push({ nextCost, nextLayer, currentNode });
103
                }
104
            }
105
        }
106
    }
107
}
108

109
int main() {
110
    // 示例输入数据
111
    int layers = 240;  // 层数
112
    int nodes = 1000;  // 每层的节点数
113

114
    // 每层的图结构 (层 -> 节点 -> 边)
115
    vector<vector<vector<Edge>>> graph(layers, vector<vector<Edge>>(nodes));
116

117
    // 构造每层的边，尽量构造平面图
118
    for (int layer = 0; layer < layers; ++layer) {
119
        for (int node = 0; node < nodes; ++node) {
120
            // 每个节点连接到下一个节点，形成一个环
121
            int nextNode = (node + 1) % nodes;
122
            graph[layer][node].push_back({ nextNode, rand() % 10 + 1 }); // 随机权重1-10
123

124
            // 添加额外的边，确保每层有5000条边以上
125
            for (int i = 0; i < 5; ++i) {
126
                int randomNode = rand() % nodes;
127
                if (randomNode != node) {
128
                    graph[layer][node].push_back({ randomNode, rand() % 10 + 1 });
129
                }
130
            }
131
        }
132
    }
133

134
    // 定义层间连接关系的稀疏存储结构
135
    InterLayerConnections interLayerCost(layers);
136

137
    // 构造层间连接代价
138
    for (int layer = 0; layer < layers - 1; ++layer) {
139
        for (int node = 0; node < nodes; ++node) {
140
            // 只有三分之一的节点有层间连接
141
            if (rand() % 3 == 0) {
142
                int cost = rand() % 2000 + 1000; // 随机权重1000-3000
143
                interLayerCost[layer][node].push_back({ layer + 1, cost }); // 当前层到下一层
144
                interLayerCost[layer + 1][node].push_back({ layer, cost }); // 下一层到当前层
145
            }
146
        }
147
    }
148

149
    // 最后一层连接回第一层
150
    for (int node = 0; node < nodes; ++node) {
151
        if (rand() % 3 == 0) {
152
            int lastCost = rand() % 2000 + 1000; // 随机权重10-30
153
            interLayerCost[layers - 1][node].push_back({ 0, lastCost }); // 最后一层到第一层
154
            interLayerCost[0][node].push_back({ layers - 1, lastCost }); // 第一层到最后一层
155
        }
156
    }
157

158
    // 起始节点和层
159
    int startNode = 0;
160
    int startLayer = 0;
161

162
    // 最小代价数组
163
    vector<vector<int>> minCost(layers, vector<int>(nodes, INF));
164

165
    // 运行Dijkstra算法
166
    auto startTime = chrono::high_resolution_clock::now(); // 开始计时
167

168
    dijkstra(startLayer, startNode, graph, interLayerCost, minCost);
169

170
    auto endTime = chrono::high_resolution_clock::now(); // 结束计时
171
    auto duration = chrono::duration_cast<chrono::milliseconds>(endTime - startTime);
172
    cout << "Total Dijkstra computation time: " << duration.count() << " ms" << endl;
173

174
    return 0;
175
}