1.为什么bellman-ford是 if(dist[n] > 0x3f3f3f/2) return -1; ，spfa却是 ==

在最短路径算法中，dist[n]的判定条件差异源于两种算法处理负权边时的不同特性，这是精心设计的正确行为。以下是详细解释：

1. Bellman-Ford算法的判定逻辑

if(dist[n] > 0x3f3f3f3f / 2) return -1;

原因：
- 负权边会导致距离”收缩”：即使从起点不可达，负权边仍然可能将初始的0x3f3f3f3f（无穷大）减小
- 示例：
- 假设存在边 u → v，权值为-10000
- 初始时 dist[u] = 0x3f3f3f3f（不可达）
- 松弛操作后 dist[v] = min(0x3f3f3f3f, 0x3f3f3f3f - 10000)
- 结果 dist[v] 会比 0x3f3f3f3f 小，但仍表示不可达
- 安全阈值：0x3f3f3f3f / 2 ≈ 1e9，远大于题目中边权的最大绝对值（10000）

2. SPFA算法的判定逻辑

if(dist[n] == 0x3f3f3f3f) return -1;

原因：
- 动态更新的特性：SPFA中节点只会被实际可达的松弛操作更新
- 如果一个节点未被更新过，它的距离将保持初始值 0x3f3f3f3f
- 无”虚假收缩”问题：
- 不可达节点的距离不会被负权边错误更新
- 因为SPFA通过队列管理，只有真正能缩短距离的节点才会被处理

3. 关键对比

4. 数学解释

对于Bellman-Ford，设边权最大绝对值为 W，经过 k 次松弛后：

dist[v] ≥ INF - k*W

题目保证 k*W < INF/2（因 k≤500, W≤10000 ⇒ k*W ≤ 5e6，而 INF/2 ≈ 1e9），因此：
- dist[v] > INF/2 ⇒ 该节点实际不可达

而SPFA中：

dist[v] == INF ⇔ 没有有效路径到达v

5. 代码验证

Bellman-Ford必须用 /2 的原因：

// 假设存在边 u→v (u不可达，w=-10000)
dist[v] = min(0x3f3f3f3f, 0x3f3f3f3f - 10000); 
// dist[v] = 0x3f3f3f3f - 10000 ≈ 2.1e9
// 此时 2.1e9 > 1e9 (INF/2)，正确判为不可达

SPFA保持 == 的原因：

// 对于不可达的v，SPFA不会处理其邻边
// dist[v] 始终保持 0x3f3f3f3f

6. 记忆技巧

• Bellman-Ford：像”撒网捕鱼”，可能误触不可达节点 ⇒ 需要宽容的阈值判断
• SPFA：像”精确制导”，只处理真正可达的节点 ⇒ 可用严格相等判断

这种差异反映了两种算法在处理不可达节点的根本性区别，都是正确的实现方式。

2.完整代码

#include <algorithm>
#include <iostream>
#include <queue>      // 使用队列管理待处理节点
#include <cstring>    // 使用memset初始化数组

using namespace std;

const int N = 1e5 + 10; // 最大点数+10防止越界

// 邻接表存储图
int h[N], w[N], e[N], ne[N], idx; // h:头指针数组 w:边权 e:终点 ne:下条边 idx:当前边编号
int dist[N];      // 存储起点到每个点的最短距离
bool st[N];       // 标记节点是否在队列中，避免重复入队

// 添加有向边
void add(int a, int b, int c) {
    e[idx] = b;     // 记录终点
    w[idx] = c;     // 记录边权
    ne[idx] = h[a]; // 插入链表头部
    h[a] = idx++;   // 更新头指针
}

int spfa() {
    // 初始化距离数组
    memset(dist, 0x3f, sizeof dist); // 初始设为无穷大(约1e9)
    dist[1] = 0;                     // 起点到自身距离为0

    queue<int> q;       // 存储待处理的节点
    q.push(1);          // 起点入队
    st[1] = true;       // 标记起点在队列中

    while (!q.empty()) {
        int t = q.front(); // 取出队首节点
        q.pop();
        st[t] = false;     // 标记该节点已出队

        // 遍历该节点的所有邻接边
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i]; // 邻接节点编号
            // 松弛操作：尝试用当前边缩短距离
            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i]; // 更新距离
                // 如果节点j不在队列中，则加入队列
                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return dist[n]; // 返回到达n号点的最短距离
}

int main() {
    scanf("%d%d", &n, &m); // 读入点数和边数

    // 初始化邻接表头指针
    memset(h, -1, sizeof h); // -1表示空指针

    // 读入所有边
    while (m--) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c); // 添加有向边
    }

    int t = spfa(); // 执行SPFA算法

    // 判断结果并输出
    if (t == 0x3f3f3f3f)  // 注意这里是严格等于
        puts("impossible"); // 不可达
    else
        printf("%d\n", t);  // 输出最短距离

    return 0;
}