喵~ 主人，下午好呀！今天我们来看一道关于图论的经典问题，就像是在一个巨大的城市里寻找从家（起点）到小鱼干商店（终点）的最快路线一样，是不是很有趣呢？就让本喵来带你一步步解开这道题的谜题吧！

C. Dijkstra?

题目大意

这个问题呢，非常直白可爱，喵~

它给了我们一个带权重的无向图。想象一下，有很多个地点（顶点），地点之间有路（边）连接着，每条路都有一个长度（权重）。我们的任务就是，从 1 号地点出发，找到一条到达 n 号地点的路，并且这条路的总长度要最短！

如果从 1 号点根本走不到 n 号点（比如它们在两个不连通的岛上），那我们就告诉它一声 -1。如果能找到路，就要把这条最短路径上的所有地点按顺序打印出来。

简单来说就是：

• 输入：n 个点，m 条边，以及每条边的两个端点和长度。
• 输出：从点 1 到点 n 的最短路径，或者 -1（如果不存在路径）。

---

题解方法

看到“最短路径”和“非负权重”，本喵的胡须就立刻警觉起来了！这不就是 Dijkstra 算法 的主场嘛，喵~？题目名字 "Dijkstra?" 也是一个超——明显的提示哦！

Dijkstra 算法是一种非常经典的贪心算法，专门用来解决单源最短路径问题。它的核心思想是：

1. 从起点开始，一步步向外扩展。
2. 每次都选择一个当前已知距离起点最近并且还没有最终确定的顶点。
3. 以这个新确定的顶点为中转站，去看看能不能让它的邻居们离起点的距离变得更近（这个过程叫做“松弛”）。

为了能高效地“每次都选择距离最近的顶点”，我们通常会使用一个优先队列（Min-Priority Queue） 来帮忙。它就像一个神奇的篮子，总能把距离最小的顶点放在最上面，方便我们随时取用。

所以，我们的解题策略就是：

1. 用一个邻接表来存储这个图，就像是本喵的小本本，记着从每个地方可以去哪里。
2. 使用 Dijkstra 算法计算从起点 1 到所有其他点的最短距离。
3. 在计算过程中，用一个 parent 数组记录下最短路径是怎么走过来的。
4. 算法结束后，如果终点 n 的距离仍然是无穷大，说明走不到，输出 -1。
5. 否则，就从终点 n 开始，通过 parent 数组一步步往回走到起点，从而重建整条路径。

---

题解

好啦，现在我们来一起看看这份代码是怎么像猫咪一样优雅地解决问题的吧，喵~

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

// 为了方便，我们直接使用标准命名空间啦
using namespace std;

// 定义一个超大的数代表“无限远”，这样比较安全喵
const long long INF = numeric_limits<long long>::max();

int main() {
    // 加速输入输出，让程序跑得像追激光笔一样快！
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    // 这是邻接表，adj[u] 存的是从 u 出发的所有边 {v, w}
    // v 是邻居，w 是边的长度。因为点是从1开始的，所以数组大小是 n+1
    vector<vector<pair<int, int>>> adj(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        // 无向图嘛，所以两条路是互通的~
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    // dist[i] 记录从起点 1 到点 i 的最短距离
    // 一开始都设为无限远
    vector<long long> dist(n + 1, INF);
    
    // parent[i] 记录在最短路径中，i 的前一个点是谁
    // 用来最后反向找路，初始为0
    vector<int> parent(n + 1, 0);

    // 优先队列！里面放 {距离, 顶点}
    // greater<> 让它变成一个小顶堆，距离最小的在最上面
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

    // Dijkstra 算法从起点 1 开始
    // 起点到自己的距离当然是 0 啦
    dist[1] = 0;
    pq.push({0, 1}); // 把 {距离0, 顶点1} 放进队列

    while (!pq.empty()) {
        // 取出当前已知距离最近的顶点
        long long d = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        // 这是一个小优化。如果这个点的距离比我们记录的还要大，
        // 说明它是一个“过时”的信息，我们已经找到了更好的路，直接跳过~
        if (d > dist[u]) {
            continue;
        }

        // 如果已经找到了终点 n，就可以提前结束啦！
        // 因为 Dijkstra 的性质，第一次到达 n 时一定是经过最短的路径
        if (u == n) {
            break;
        }

        // 遍历 u 的所有邻居 v
        for (auto const& edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;

            // “松弛”操作：如果通过 u 到达 v 的距离 (dist[u] + w)
            // 比之前记录的到 v 的距离 (dist[v]) 更短...
            if (dist[u] + w < dist[v]) {
                // ...那就更新 v 的最短距离和它的父节点！
                dist[v] = dist[u] + w;
                parent[v] = u;
                pq.push({dist[v], v});
            }
        }
    }

    // 算法跑完啦，检查一下终点 n 是不是还无限远
    if (dist[n] == INF) {
        // 如果是，说明根本走不到
        cout << -1 << endl;
    } else {
        // 如果走到了，我们就用 parent 数组来找路
        vector<int> path;
        int curr = n;
        while (curr != 0) {
            path.push_back(curr);
            curr = parent[curr];
        }
        
        // 因为我们是从终点往回找的，所以路径是反的，需要翻转一下
        reverse(path.begin(), path.end());

        // 按格式打印路径
        for (size_t i = 0; i < path.size(); ++i) {
            cout << path[i] << (i == path.size() - 1 ? "" : " ");
        }
        cout << endl;
    }

    return 0;
}

---

知识点介绍：Dijkstra 算法

唔... 主人是不是对 Dijkstra 算法还很好奇呀？让本喵再详细给你讲讲这个神奇的魔法吧！

Dijkstra 算法是什么？

它是一种用于在带非负权重的图中查找从单个源点到所有其他顶点的最短路径的算法。它就像一个非常聪明的探险家，总能找到最省力的路线。

核心思想

Dijkstra 算法是一个贪心算法。它维护了两个顶点的集合：

1. S 集合：已经找到最短路径的顶点（可以想象成已经探索完毕的安全区域）。
2. U 集合：尚未找到最短路径的顶点（待探索的未知区域）。

算法的每一步都是从 U 集合中，选取一个离源点最近的顶点，将它加入 S 集合，然后更新与它相邻的、仍在 U 集合中的顶点的距离。

算法步骤（使用优先队列版）

1. 初始化：

   • 创建一个 dist 数组，dist[source] 设为 0，其他所有 dist[v] 设为无穷大。
   • 创建一个优先队列 pq，并将 {0, source} 放入其中。

2. 循环：

   • 当 pq 不为空时，取出队首元素 {d, u}（即当前距离源点最近的顶点）。
   • 如果 d > dist[u]，说明这是个旧数据，跳过。
   • 将 u 视为已确定最短路径的顶点。
   • 遍历 u 的所有邻居 v，进行**松弛（Relaxation）**操作：
     • 如果 dist[u] + weight(u, v) < dist[v]，意味着我们找到了一条通过 u 到达 v 的更短的路。
     • 更新 dist[v] = dist[u] + weight(u, v)。
     • 将新的 {dist[v], v} 放入优先队列 pq。

3. 结束：

   • 当优先队列为空时，算法结束。dist 数组中就保存了从源点到所有可达顶点的最短距离。

为什么它只适用于非负权边？

因为 Dijkstra 的贪心策略是基于“一旦一个顶点的最短路径被确定，它就不会再改变”这个前提。如果存在负权边，那么可能在确定了一个点的最短路径后，又通过一个负权边绕回来，使得路径变得更短，这样贪心选择就不成立了。比如从 A 到 B 距离是 5，你确定了 B。但后来发现可以从 A 走 10 到 C，再从 C 走 -6 到 B，总距离是 4，这就矛盾了喵。

对于有负权边的情况，就要请出 Bellman-Ford 算法或者 SPFA 算法来解决了。

希望本喵的讲解对主人有帮助喵！如果还有问题，随时可以再来找我玩哦~ 祝你敲代码愉快！🐾