【Bellman-Ford】High Score
题目翻译
你玩一个包含 n 个房间和 m 条隧道的游戏。初始分数为 0，每条隧道会使分数增加 x（x 可正可负），且可以多次穿过同一条隧道。
你的任务是从 1 号房间走到 n 号房间，求能获得的最大分数。如果能获得无限大的分数，输出 - 1。
输入说明
- 第一行输入两个整数 n 和 m，分别表示房间数和隧道数（房间编号为 1 到 n）。
- 接下来 m 行，每行三个整数 a、b、x，表示一条从 a 到 b 的单向隧道，穿过该隧道分数增加 x。
- 保证从 1 号房间能到达 n 号房间。
输出说明
输出最大分数；若能获得无限大分数，输出 - 1。
样例输入
复制
4 5 1 2 3 2 4 -1 1 3 -2 3 4 7 1 4 4样例输出
复制
5
Bellman-Ford
Bellman-Ford 算法是一种用于求解单源最短路径问题的经典算法，由理查德・贝尔曼（Richard Bellman）和莱斯特・福特（Lester Ford）提出。它的核心思想是通过松弛操作逐步优化从起点到其他所有节点的最短路径估计值，最终得到精确解。
与 Dijkstra 算法不同，Bellman-Ford 算法支持含负权边的图，但无法处理存在从起点可达的负环（即环的总权值为负数，且从起点能到达该环）的情况（此时最短路径不存在，因为可以无限绕环减小路径权值）。
Bellman-Ford 算法的基本原理
问题场景
给定一个带权有向图（边权可正可负）和一个起点，求起点到其他所有节点的最短路径。核心操作：松弛（Relaxation）
对于每条边(u, v)（从节点 u 到 v，权值为 w），如果从起点到 u 的当前最短路径长度dist[u]加上 w，小于从起点到 v 的当前最短路径长度dist[v]，则更新dist[v]：dist[v] = dist[u] + w
这一操作称为 “松弛”，因为它可能缩短了到 v 的路径。执行步骤
- 初始化：
dist[起点] = 0，其余节点的dist为无穷大（表示初始时无法到达）。 - 对所有边重复执行
n-1次松弛操作（n 为节点总数）。因为在不含负环的图中，最长的最短路径最多包含n-1条边（否则会出现环，而环的权值非负时可去掉）。 - 检测负环：在完成
n-1次松弛后，再对所有边执行一次松弛。如果仍能更新某个dist[v]，说明存在从起点可达的负环（因为正常情况下n-1次松弛已足够得到最优解，若还能更新则意味着可通过绕负环无限缩短路径）。
- 初始化：
拆解每一步：
外层循环（n-1 次）：
为什么要重复 n-1 次？因为从房间 1 到任意房间的最长路径，最多经过n-1个房间（如果超过 n-1 个，必然绕圈，而绕圈如果是正收益会被后续检测为正环）。所以 n-1 次足够让所有可能的 “不绕圈路径” 都参与更新。内层循环（遍历所有隧道）：
每次都检查每一条隧道a→b（从 a 到 b，收益 x），看是否能通过这条隧道让到达 b 的分数更高。松弛条件：
dist[a] != LLONG_MIN：确保我们已经知道 “到达 a 的有效分数”（a 是可达的）。dist[b] < dist[a] + x：如果 “从 1 到 a 的分数 + 隧道 a→b 的收益” 比 “当前已知的 1 到 b 的分数” 更高，说明找到了一条更好的路径。
更新操作：
把dist[b]更新为这个更高的分数，相当于 “记录下这条更好的路径”。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;int n,m;int main()
{cin>>n>>m;vector<tuple<int,int,int>>edge;vector<vector<int>>re(n+1);for(int i=0;i<m;++i){int a,b,x;cin>>a>>b>>x;edge.emplace_back(a,b,x);re[b].push_back(a);}vector<ll>dis(n+1,LLONG_MIN);dis[1]=0;for(int i=0;i<n;++i)for(auto [a,b,x]:edge)if(dis[a]!=LLONG_MIN&&dis[a]+x>dis[b])dis[b]=dis[a]+x;vector<int>canend(n+1,0);canend[n]=1;queue<int>q;q.push(n);while(!q.empty()){int u=q.front();q.pop();for(auto v:re[u]){if(!canend[v]){canend[v]=1;q.push(v);}}}int f=0;for(auto [a,b,x]:edge){if(dis[a]!=LLONG_MIN&&dis[a]+x>dis[b]&&canend[b]){f=1;break;}}if(!f)cout<<dis[n];else cout<<"-1";return 0;
}SPFA 算法（Shortest Path Faster Algorithm）。SPFA 通过队列只处理那些距离发生变化的节点，减少了不必要的松弛操作，效率通常比标准的 Bellman-Ford 更高。
超时
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;int n,m;int main()
{cin>>n>>m;vector<vector<pair<int,int>>>edge(n+1);vector<vector<int>>re(n+1);for(int i=0;i<m;++i){int a,b,x;cin>>a>>b>>x;edge[a].emplace_back(b,x);re[b].push_back(a);}vector<ll>dis(n+1,LLONG_MIN);dis[1]=0;vector<int>to_end(n+1,0);to_end[n]=1;queue<int>q;q.push(n);while(!q.empty()){int u=q.front();q.pop();for(auto v:re[u]){if(!to_end[v]){to_end[v]=1;q.push(v);}}}vector<int>in_go(n+1,0);vector<int>cnt(n+1,0);queue<int>go;go.push(1);in_go[1]=1;cnt[1]=1;int circle=0;while(!go.empty()&&!circle){int u=go.front();go.pop();in_go[u]=0;for(auto [v,x]:edge[u]){if(dis[u]!=LLONG_MIN&&dis[u]+x>dis[v]){dis[v]=dis[u]+x;if(!in_go[v]){in_go[v]=1;go.push(v);cnt[v]++;if(cnt[v]>n&&to_end[v]){circle=1;break;}}}}}if(circle)cout<<"-1";else cout<<dis[n];return 0;
}