如何使用C++解决带有限制条件(A到B不可行,B到F不可行,D到G不可行)的第二道题?请提供一个完整的示例代码,并确保程序运行后能输出结果为:从A到H最短时间为:0.565 最快路线为A->D->E->F->H
时间: 2024-10-21 18:12:10 浏览: 44
为了处理带有限制条件的“最快路线问题”,我们可以通过在初始化阶段将这些限制条件对应的边权重设为无穷大来实现。以下是完整的C++代码示例:
```cpp
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <limits>
using namespace std;
const int INF = numeric_limits<int>::max();
void dijkstra(const vector<vector<pair<int, double>>>& graph, int start, vector<double>& dist, vector<int>& prev) {
int n = graph.size();
dist.assign(n, INF);
prev.assign(n, -1);
dist[start] = 0;
priority_queue<pair<double, int>, vector<pair<double, int>>, greater<>> pq;
pq.push({0, start});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue;
for (auto& [v, w] : graph[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
prev[v] = u;
pq.push({dist[v], v});
}
}
}
}
void printPath(const vector<int>& prev, int target) {
if (prev[target] == -1) {
cout << "A";
return;
}
printPath(prev, prev[target]);
cout << "->" << char('A' + target);
}
int main() {
const int n = 8; // 城市数量
vector<vector<pair<int, double>>> graph(n);
// 添加边及其权重(时间)
graph[0].emplace_back(1, 9.0 / 40); // A to B
graph[0].emplace_back(2, 7.0 / 50); // A to C
graph[0].emplace_back(3, 9.0 / 80); // A to D
graph[1].emplace_back(2, 6.0 / 50); // B to C
graph[1].emplace_back(4, 12.0 / 50); // B to E
graph[1].emplace_back(5, 12.0 / 40); // B to F
graph[2].emplace_back(3, 8.0 / 50); // C to D
graph[2].emplace_back(4, 9.0 / 50); // C to E
graph[3].emplace_back(4, 10.0 / 50); // D to E
graph[3].emplace_back(6, 10.0 / 30); // D to G
graph[4].emplace_back(5, 7.0 / 50); // E to F
graph[4].emplace_back(6, 8.0 / 50); // E to G
graph[4].emplace_back(7, 7.0 / 20); // E to H
graph[5].emplace_back(7, 9.0 / 80); // F to H
graph[6].emplace_back(7, 11.0 / 80); // G to H
// 处理限制条件
graph[0][0].second = INF; // A to B
graph[1][2].second = INF; // B to F
graph[3][1].second = INF; // D to G
vector<double> dist;
vector<int> prev;
dijkstra(graph, 0, dist, prev);
cout << "从A到H最短时间为:" << fixed << setprecision(3) << dist[7] << endl;
cout << "最快路线为: ";
printPath(prev, 7);
cout << endl;
return 0;
}
```
### 解释
1. **图的构建**: 使用邻接列表 `graph` 来存储图,其中每个节点是一个 `pair<int, double>`,分别表示目标节点和到达该节点的时间。
2. **Dijkstra算法**: 实现了Dijkstra算法来找到从起点A到终点H的最短时间路径。
3. **限制条件处理**: 在添加边时,直接将限制条件对应的边的权重设为 `INF`,这样这些边不会被选入最短路径中。
4. **路径打印**: 使用递归函数 `printPath` 来打印从起点到终点的路径。
运行上述代码,输出结果应为:
```
从A到H最短时间为:0.565
最快路线为: A->D->E->F->H
```
阅读全文