为了帮助Bob找到从城市1到城市N的最短路径，同时保证花费不超过K枚金币，我们可以使用一种称为“扩展的Dijkstra算法”的方法。这个算法不仅考虑路径长度，还考虑路径的费用。
以下是C++代码实现：
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <climits>
using namespace std;
struct Edge {
int destination;
int length;
int cost;
};
struct State {
int city;
int length;
int cost;
bool operator>(const State& other) const {
return length > other.length;
}
};
int findShortestPath(int K, int N, int R, vector<vector<Edge>>& graph) {
vector<vector<int>> dist(N + 1, vector<int>(K + 1, INT_MAX));
priority_queue<State, vector<State>, greater<State>> pq;
dist[1][0] = 0;
pq.push({1, 0, 0});
while (!pq.empty()) {
State current = pq.top();
pq.pop();
int currentCity = current.city;
int currentLength = current.length;
int currentCost = current.cost;
if (currentCity == N) {
return currentLength;
}
for (const Edge& edge : graph[currentCity]) {
int nextCity = edge.destination;
int nextLength = currentLength + edge.length;
int nextCost = currentCost + edge.cost;
if (nextCost <= K && nextLength < dist[nextCity][nextCost]) {
dist[nextCity][nextCost] = nextLength;
pq.push({nextCity, nextLength, nextCost});
}
}
}
return -1;
}
int main() {
int K, N, R;
cin >> K >> N >> R;
vector<vector<Edge>> graph(N + 1);
for (int i = 0; i < R; ++i) {
int S, D, L, T;
cin >> S >> D >> L >> T;
graph[S].emplace_back(Edge{D, L, T});
}
int result = findShortestPath(K, N, R, graph);
cout << result << endl;
return 0;
}
测试用例
-
基本测试用例
-
无可行路径
-
直接到达
- 输入：
5
2
1
1 2 3 2
- 输出：
3
- 解释：直接从1到2，总长度为3，总费用为2。
-
多条路径选择
通过这些测试用例，我们可以验证代码的正确性和鲁棒性。