问题本质

• 无向正权图，求 $1 \rightarrow n$ 的最短路径，输出路径（任意可行解即可）。
• 无路径输出 $-1$。

算法选择

• 边权为正 → 必须用 Dijkstra（不能直接用 BFS，因为边权不一定为 $1$）。
• 朴素 Dijkstra 时间复杂度 $O(n^2)$ 会超时（$n \le 10^5$），必须用 堆优化（优先队列）实现，复杂度 $O((n+m)\log n)$。

关键点

1. 记录前驱（predecessor）
   用 $prev[v]$ 表示从源点 $1$ 到 $v$ 的最短路径上 $v$ 的前一个顶点。
   当通过节点 $u$ 更新 $dist[v]$ 时，同时更新 $prev[v] = u$。

2. 输出路径
   从 $n$ 开始反向追溯 $prev$ 直到 $1$，将节点存入数组，最后逆序输出。
   注意路径至少包含 $1$ 和 $n$（如果不连通则输出 $-1$）。

3. 处理图的特性

   • 自环：不会更新更短路径（因为边权 $\ge 1$，不可能比不走自环更短），可忽略。
   • 多重边：Dijkstra 自然处理，取最短权重即可（堆优化会优先弹出最短边）。

4. 初始化与边界

   • $dist[1] = 0$，其余 $dist = \infty$。
   • 堆中初始放入 $(0, 1)$。
   • 如果最后 $dist[n] = \infty$，输出 $-1$。

复杂度

• 时间：$O((n+m)\log n)$
• 空间：邻接表 $O(n+m)$，距离/前驱数组 $O(n)$，完全符合 $64$ MB 限制。

实现注意事项

• 用 vector<pair<int, long long>> 或 vector<tuple<int, int>> 存邻接表。