C++ 实现加权有向图中指定边数路径的最小成本算法

#include #include #include #include <limits.h> using namespace std;

// 定义边 struct Edge { int to, cost; Edge(int t, int c): to(t), cost(c) {} };

// 定义邻接表 typedef vector<vector> AdjList;

// Dijkstra算法 int dijkstra(const AdjList& graph, int source, int destination, int m) { int n = graph.size(); vector dist(n, INT_MAX); // 到各点的距离 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 小根堆 dist[source] = 0; pq.push(make_pair(0, source)); while (!pq.empty()) { int u = pq.top().second; int w = pq.top().first; pq.pop(); if (u == destination && w <= m) { // 找到符合要求的路径 return dist[u]; } if (w > m) { // 达到路径边数限制 break; } if (dist[u] < w) { // 路径长度已经超过当前距离 continue; } for (const auto& e : graph[u]) { int v = e.to; int nw = w + e.cost; if (nw <= m && dist[v] > nw) { // 符合要求的路径 dist[v] = nw; pq.push(make_pair(nw, v)); } } } return INT_MAX; }

int main() { int n, e; cin >> n >> e; AdjList graph(n); for (int i = 0; i < e; i++) { int u, v, w; cin >> u >> v >> w; graph[u].push_back(Edge(v, w)); } int source, destination, m; cin >> source >> destination >> m; int ans = dijkstra(graph, source, destination, m); if (ans == INT_MAX) { cout << 2147483647 << endl; } else { cout << ans << endl; } return 0; }