18732 最短路问题

### 思路

1. **建模问题**：将车站和公交线路建模为图，其中车站是节点，公交线路是带权边。
2. **选择算法**：使用Dijkstra算法求解从车站1到车站n的最短路径问题。
3. **初始化**：创建一个优先队列（最小堆）来存储当前节点和到达该节点的最小花费。初始化所有节点的最小花费为无穷大，起点车站1的花费为0。
4. **更新节点**：从优先队列中取出当前花费最小的节点，更新其邻接节点的最小花费，并将更新后的节点重新加入优先队列。
5. **终止条件**：当处理到车站n时，输出其最小花费；如果优先队列为空且未处理到车站n，输出-1。

### 伪代码

```
function dijkstra(n, m, edges):
    create a priority queue pq
    create a list dist of size n+1, initialized to infinity
    dist[1] = 0
    pq.push((0, 1))  // (cost, node)

    while pq is not empty:
        (current_cost, u) = pq.pop()
        if u == n:
            return current_cost
        if current_cost > dist[u]:
            continue
        for each (v, cost) in edges[u]:
            if dist[u] + cost < dist[v]:
                dist[v] = dist[u] + cost
                pq.push((dist[v], v))

    return -1
```

### C++代码

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

using namespace std;

const int INF = 1e9; // Define a large constant value for infinity

struct Edge {
    int to, cost;
};

int dijkstra(int n, int m, vector<vector<Edge>>& graph) {
    vector<int> dist(n + 1, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    dist[1] = 0;
    pq.push(make_pair(0, 1));

    while (!pq.empty()) {
        pair<int, int> top = pq.top();
        int current_cost = top.first;
        int u = top.second;
        pq.pop();

        if (u == n) {
            return current_cost;
        }

        if (current_cost > dist[u]) {
            continue;
        }

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

    return -1;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<Edge>> graph(n + 1);

    for (int i = 0; i < m; ++i) {
        int a, b, x;
        cin >> a >> b >> x;
        graph[a].push_back({b, x});
        graph[b].push_back({a, x});
    }

    int result = dijkstra(n, m, graph);
    cout << result << endl;

    return 0;
}

### 总结

1. **问题建模**：将车站和公交线路建模为图，使用Dijkstra算法求解最短路径问题。
2. **算法选择**：Dijkstra算法适用于边权非负的最短路径问题，使用优先队列（最小堆）优化。
3. **实现细节**：初始化所有节点的最小花费为无穷大，起点车站1的花费为0。使用优先队列存储当前节点和到达该节点的最小花费，逐步更新邻接节点的最小花费。
4. **终止条件**：当处理到车站n时，输出其最小花费；如果优先队列为空且未处理到车站n，输出-1。

原文地址：https://blog.csdn.net/huang1xiao1sheng/article/details/142738701

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！