帮助Bob找到从城市1到城市N的最短路径算法实现

问题：

用C++解决以下问题，并设计测试用例：有N个城市与R条单向道路相连。每条路都有两个参数：长度和通行费(以金币数量表示)Bob 由于Alice 在取牌游戏中作弊，便与他分道扬。Bob 曾经住在城市1，现在决定搬到N号城市，他想尽快到达那里，但他只有K枚金币。我们想帮助Bob 找到从城市1 到城市V的最短路径，花费不超过 K。Input输入的第一行包含整数K，（0≤K≤10000），Bob可以在途中花费的最大硬币数。第二行包含整数N，（2≤N≤100），即城市总数。第三行包含整数 R，（1≤ R≤10000），道路总数。以下每一行通过指定由单个空白字符分隔的整数 S、D、L 和 T 来描述一条道路:＊S是起点城市，1≤S≤ND 是终点城市，1≤D≤N＊L 是道路长度，1≤L≤100T是通行费（以硬币数量表示），〇≤T≤100请注意，不同的道路可能具有相同的源城市和目标城市。输出一行一个整数，表示最短路径，保证花费不超过K。如果不存在请输出一1。

答案：

为了帮助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;
}

测试用例

基本测试用例
- 输入：
```
10
4
5
1 2 5 3
2 3 4 2
3 4 3 1
1 3 10 5
2 4 8 4
```
- 输出：
```
12
```
- 解释：路径为1 -> 2 -> 3 -> 4，总长度为12，总费用为6。
无可行路径
- 输入：
```
1
3
3
1 2 2 2
2 3 2 2
1 3 5 5
```
- 输出：
```
-1
```
- 解释：没有任何路径的费用在1金币以内。
直接到达
- 输入：
```
5
2
1
1 2 3 2
```
- 输出：
```
3
```
- 解释：直接从1到2，总长度为3，总费用为2。
多条路径选择
- 输入：
```
10
5
6
1 2 2 1
2 3 2 1
3 4 2 1
4 5 2 1
1 3 5 2
3 5 3 2
```
- 输出：
```
8
```
- 解释：路径为1 -> 2 -> 3 -> 4 -> 5，总长度为8，总费用为4。

通过这些测试用例，我们可以验证代码的正确性和鲁棒性。

帮助Bob找到从城市1到城市N的最短路径算法实现

使用 GPT-4o 回答，作者 GPT4oMini.app

测试用例