Dijkstra算法的应用(算法思想)

有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。

输入格式:
输入说明：输入数据的第 1 行给出 4 个正整数 n、m、s、d，其中 n（2≤n≤500）是城市的个数，顺便假设城市的编号为 0~(n−1)；m 是高速公路的条数；s 是出发地的城市编号；d 是目的地的城市编号。随后的 m 行中，每行给出一条高速公路的信息，分别是：城市 1、城市 2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过 500。输入保证解的存在。

输出格式:
在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。

该题适用于Dijkstra算法，Dijkstra算法是一种用于寻找图中单源最短路径的经典算法。适用于没有负权边的图。本题除了寻找从出发点到目的地之间的最短路径，还要在多条最短路径中选择总费用最低的一条。
本题算法思想如下：

1. 初始化：为每个结点设置初始的距离值，初始的过路费值，为每个结点设置一个前驱节点，创建一个访问标记数组，用于记录被处理过的结点；
2. 主循环：每次迭代中，从未访问的结点中选择一个距离最小的结点，将该节点标记为已访问。更新该节点的所有邻居节点的距离和过路费，此时，如果通过当前节点到达邻居节点的新路径比已知路径更短，更新邻居节点的距离和过路费，并更新前驱节点；如果新节点与一直路径长度相同但是过路费更低，则更新邻居节点的过路费，并更新前驱节点。
3. 终止 ：当所有结点都被访问过，或者目标节点已经被访问时，算法终止。
4. 输出：通过前驱节点数组回溯路径，输出从起点到终点的最短路径，总距离和过路费。

以下为完整代码：

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

const int INF = 1000000;  // 定义一个很大的数表示无穷大

struct Edge {
    int to;       // 目标城市
    int distance; // 高速公路长度
    int toll;     // 过路费
};

// 比较器，用于优先队列
struct CompareCost {
    bool operator()(const pair<int, int>& left, const pair<int, int>& right) {
        if (left.first == right.first) {
            return left.second > right.second; // 如果总成本相同，比较过路费
        }
        return left.first > right.first; // 否则，比较总成本
    }
};

void dijkstra(const vector<vector<Edge>>& graph, int start, int end) {
    int n = graph.size();
    vector<int> dist(n, INF);  // 最短距离
    vector<int> cost(n, INF);  // 最低过路费
    vector<int> prev(n, -1);   // 前驱节点
    vector<bool> visited(n, false);  // 访问标记

    dist[start] = 0;
    cost[start] = 0;

    // 优先队列
    priority_queue<pair<int, int>, vector<pair<int, int>>, CompareCost> pq;
    pq.push({0, start});  // (total cost, current node)

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

        if (visited[currentNode]) continue;

        visited[currentNode] = true;

        for (const auto& edge : graph[currentNode]) {
            int newDistance = dist[currentNode] + edge.distance;
            int newToll = cost[currentNode] + edge.toll;
            int newTotalCost = newDistance + newToll;

            if (newDistance < dist[edge.to]) {
                dist[edge.to] = newDistance;
                cost[edge.to] = newToll;
                prev[edge.to] = currentNode;
                pq.push({newTotalCost, edge.to});
            } else if (newDistance == dist[edge.to] && newToll < cost[edge.to]) {
                cost[edge.to] = newToll;
                prev[edge.to] = currentNode;
                pq.push({newTotalCost, edge.to});
            }
        }
    }

    // 输出结果
    if (dist[end] == INF) {
        cout << "No path found" << endl;
    } else {
        cout << dist[end] << " " << cost[end] << endl;
    }
}

int main() {
    int n, m, s, d;
    cin >> n >> m >> s >> d;

    vector<vector<Edge>> graph(n);

    for (int i = 0; i < m; ++i) {
        int u, v, length, toll;
        cin >> u >> v >> length >> toll;
        graph[u].push_back({v, length, toll});
        graph[v].push_back({u, length, toll});  // 无向图
    }

    dijkstra(graph, s, d);

    return 0;
}