思路与算法

用邻接表保存无向图，重边和自环原样保留。dist[1]=0，其余为无穷大，把(0,1)加入最小堆。反复取出距离最小的条目，若它已经不是当前dist就跳过；否则枚举出边，找到更短距离时更新并压堆。最后输出dist[N]。

正确性说明

所有边权为正，当前最小且未过期的堆条目不可能通过更远节点再得到更短路径，因此其距离可按Dijkstra性质确定。每次松弛保持dist是某条实际路径的长度，不会低估最短距离。最短路径上各前驱被依次处理，确保最优距离最终传播到N。过期条目仅代表已被更短路径替代的旧信息，跳过不影响结果。

复杂度

邻接表和dist初始化O(N+M)。使用允许重复条目的堆，最坏O((N+M)log(N+M))时间，邻接表、距离及堆共O(N+M)空间。N≤10^5、M≤5×10^5；正权最短简单路径最多N-1条边、边长≤1000，用long long并预留无穷大。

易错点

无向边要插入两个方向；自环和重边合法，不能因重复就覆盖为较差边。N=1时距离为0。题目保证1至N可达，因此不用擅自定义无解输出。尽管标题提Spfa，实际采用满足完整规模的堆优化Dijkstra。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> g(n);
    for (int i = 0, u, v, w; i < m; ++i) {
        cin >> u >> v >> w;
        g[--u].push_back({--v, w});
        g[v].push_back({u, w});
    }
    const long long INF = 1LL << 60;
    vector<long long> d(n, INF);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>,
                   greater<pair<long long, int>>>
        q;
    d[0] = 0;
    q.push({0, 0});
    while (!q.empty()) {
        auto cur = q.top();
        q.pop();
        int u = cur.second;
        if (cur.first != d[u])
            continue;
        for (auto e : g[u])
            if (d[e.first] > cur.first + e.second) {
                d[e.first] = cur.first + e.second;
                q.push({d[e.first], e.first});
            }
    }
    cout << d[n - 1] << '\n';
}