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 infinitystruct 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。