使用C++实现以上程序,并且可以直接复制到编译器上运行的
时间: 2024-03-14 07:43:32 浏览: 104
好的,以下是用 C++ 实现的代码,可以直接复制到编译器上运行:
```c++
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;
vector<int> dijkstra(unordered_map<int, unordered_map<int, int>>& graph, int start, int end) {
priority_queue<pair<int, vector<int>>, vector<pair<int, vector<int>>>, greater<pair<int, vector<int>>>> pq;
unordered_map<int, int> dist;
vector<int> path;
pq.push(make_pair(0, vector<int>{start}));
while (!pq.empty()) {
auto curr = pq.top();
pq.pop();
int node = curr.second.back();
if (node == end) {
path = curr.second;
break;
}
int cost = curr.first;
if (!dist.count(node)) {
dist[node] = cost;
for (auto& neighbor : graph[node]) {
int next_node = neighbor.first;
int next_cost = neighbor.second;
vector<int> new_path = curr.second;
new_path.push_back(next_node);
pq.push(make_pair(cost + next_cost, new_path));
}
}
}
return path;
}
int main() {
int n, m;
cin >> n >> m;
unordered_map<int, unordered_map<int, int>> graph;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
graph[u][v] = 1; // 假设所有路径长度都为1
}
vector<int> path = dijkstra(graph, 1, n);
for (int i = 0; i < path.size(); i++) {
cout << path[i];
if (i != path.size() - 1) {
cout << "->";
}
}
cout << endl;
return 0;
}
```
这里使用了 `unordered_map` 存储图,因为 C++ 的标准库中没有类似 Python 的字典类型。如果有任何问题,请随时向我提问。
阅读全文