用C++代码完成第二道题和第三道题

### 第二题：最快路线问题

#### 问题描述
某市民开车想从A点至H点，需要找到一条最快的路线。给定每条路的路程和速度，部分道路发生拥堵，需要计算实际行驶时间。

#### 算法思路
1. 将每条路的路程和速度转换为通过时间。
2. 使用Dijkstra算法求解单源最短路径问题，找到从A点到H点的最短时间路径。

#### C++代码实现

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

struct Edge {
    int to;
    double weight;
};

void dijkstra(vector<vector<Edge>>& graph, vector<double>& dist, int start) {
    priority_queue<pair<double, int>, vector<pair<double, int>>, greater<>> pq;
    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [currentDist, u] = pq.top();
        pq.pop();

        if (currentDist > dist[u]) continue;

        for (const auto& edge : graph[u]) {
            int v = edge.to;
            double weight = edge.weight;
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
}

int main() {
    int n = 8; // 8个节点，编号0-7
    vector<vector<Edge>> graph(n);

    // 添加边和权重
    graph[0].push_back({1, 9.0 / 40}); // A-B
    graph[0].push_back({2, 7.0 / 50}); // A-C
    graph[0].push_back({3, 9.0 / 80}); // A-D
    graph[1].push_back({2, 6.0 / 50}); // B-C
    graph[1].push_back({4, 12.0 / 50}); // B-E
    graph[1].push_back({5, 12.0 / 40}); // B-F
    graph[2].push_back({3, 8.0 / 50}); // C-D
    graph[2].push_back({4, 9.0 / 50}); // C-E
    graph[3].push_back({4, 10.0 / 50}); // D-E
    graph[3].push_back({6, 10.0 / 30}); // D-G
    graph[4].push_back({5, 7.0 / 50}); // E-F
    graph[4].push_back({6, 8.0 / 50}); // E-G
    graph[4].push_back({7, 7.0 / 20}); // E-H
    graph[5].push_back({7, 9.0 / 40}); // F-H
    graph[6].push_back({7, 11.0 / 80}); // G-H

    vector<double> dist(n, DBL_MAX);
    dijkstra(graph, dist, 0); // 从A点开始

    cout << "从A点到H点的最短时间为: " << dist[7] << "小时" << endl;

    return 0;
}

### 第三题：汽车加油问题

#### 问题描述
一辆汽车加满油后可以行驶N公里，途中经过K个加油站，需要设计一个贪心算法，确定在哪些加油站加油以使加油次数最少。

#### 算法思路
1. 每次尽量行驶到下一个能到达的最远加油站。
2. 如果无法到达下一个加油站，则在当前加油站加油。

#### C++代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> findMinRefills(int N, const vector<int>& stations) {
    vector<int> refills;
    int current_refill = 0;
    int num_stations = stations.size();

    while (current_refill <= num_stations) {
        int last_refill = current_refill;
        while (current_refill <= num_stations && stations[current_refill] - stations[last_refill] <= N) {
            current_refill++;
        }

        if (current_refill == last_refill) {
            // Cannot reach the next station
            return {};
        }

        if (current_refill <= num_stations) {
            refills.push_back(stations[last_refill]);
        }
    }

    return refills;
}

int main() {
    int N = 600; // 汽车加满油后的最大行驶距离
    vector<int> stations = {300, 500, 700, 1100, 1400, 1600, 1900, 2200}; // 加油站位置

    vector<int> refills = findMinRefills(N, stations);

    if (refills.empty()) {
        cout << "无法到达目的地" << endl;
    } else {
        cout << "在以下加油站加油可以使加油次数最少: ";
        for (int refill : refills) {
            cout << refill << " ";
        }
        cout << endl;
    }

    return 0;
}

以上代码分别实现了“最快路线问题”和“汽车加油问题”的解决方案。希望对你有帮助！