【入门】最短距离及花费

Question

描述

A国有n个城市，修建了m条道路（道路双向都可以走），每条道路的长度为d，走该路线要花费p元的过路费。

请问：如果要从编号为s的城市到编号为t的城市，最短距离是多少，如果按最短距离来走要花多少钱？

注意：如果有多条最短路，请输出花费最少的距离及花费。

输入描述

读入若干组数据，对于每组数据：

先输入n,m，城市的编号是1~n，然后是m行，每行4个数 a,b,d,p，表示a城市和b城市之间有一条边，且其长度为d，过路费花费为p。

最后一行是两个数 s,t，表示起点编号为s，终点编号为t。

当读入n和m为0时，表示输入结束。
(1<n≤1000, 0<m<100000, s != t)

输出描述

对于每组输入，输出一行有两个数， 表示最短距离及其花费。

用例输入 1

3 2
1 2 5 6
2 3 4 5
1 3
0 0
用例输出 1

9 11
来源

图论

Answer 1

以下内容由CHATGPT及阿里嘎多学长共同生成、有用望采纳：

---

这个问题可以通过使用图论中的Dijkstra算法来解决，该算法可以找到从起点到图中所有其他顶点的最短路径。然而，由于问题的特殊性，我们需要对Dijkstra算法进行一些修改，以同时考虑路径长度和花费。

算法思路

1. 构建图：首先，将输入的城市和道路转换成图的顶点和边。每条边有两个属性：长度 ( d ) 和花费 ( p )。

2. 初始化：为每个顶点设置一个初始距离和花费，将起点的距离设置为0，其他顶点的距离和花费设置为无穷大。

3. 优先队列：使用优先队列（最小堆）来选择下一个顶点，优先队列将基于当前已知的最短路径长度和花费进行排序。

4. 松弛操作：对于每个从起点可达的顶点 ( u )，检查从 ( u ) 到它的所有邻居 ( v ) 的边。如果通过 ( u ) 到达 ( v ) 的新路径比当前已知的路径更短或花费更少，则更新 ( v ) 的距离和花费。

5. 选择最短花费的路径：如果存在多条长度相同的最短路径，选择花费最少的一条。

6. 输出结果：当所有顶点都被访问过，或者到达目标顶点时，输出最短路径的长度和花费。

代码实现

以下是使用C++实现的伪代码：

#include <iostream>
#include <vector>
#include <queue>
#include <functional>

using namespace std;

struct Edge {
    int to, len, cost;
    Edge(int to, int len, int cost) : to(to), len(len), cost(cost) {}
};

struct State {
    int dist, cost;
    bool operator<(const State &other) const {
        return dist < other.dist || (dist == other.dist && cost > other.cost);
    }
};

void dijkstra(vector<vector<Edge>> &graph, int start, int end) {
    priority_queue<State, vector<State>, greater<State>> pq;
    vector<State> dists( graph.size() + 1, {INT_MAX, INT_MAX} );
    pq.push({0, 0});
    dists[start] = {0, 0};

    while (!pq.empty()) {
        int u = pq.top().dist;
        int c = pq.top().cost;
        pq.pop();

        if (u == dists[end].dist) break; // 找到最短路径

        for (auto &e : graph[u]) {
            int v = e.to;
            int newDist = dists[u].dist + e.len;
            int newCost = dists[u].cost + e.cost;

            if (newDist < dists[v].dist || (newDist == dists[v].dist && newCost < dists[v].cost)) {
                dists[v] = {newDist, newCost};
                pq.push({newDist, newCost});
            }
        }
    }

    cout << dists[end].dist << " " << dists[end].cost << endl;
}

int main() {
    int n, m;
    while (cin >> n >> m && n) {
        vector<vector<Edge>> graph(n + 1);
        for (int i = 0; i < m; ++i) {
            int a, b, d, p;
            cin >> a >> b >> d >> p;
            graph[a].emplace_back(b, d, p);
            graph[b].emplace_back(a, d, p); // 因为是无向图
        }
        int s, t;
        cin >> s >> t;
        dijkstra(graph, s, t);
    }
    return 0;
}

参考资料

1. Dijkstra算法 - 维基百科
2. C++ STL中的priority_queue - cppreference

请注意，上述代码是一个简化的示例，实际应用中可能需要更多的错误检查和优化。