此篇主要是记录关于spfa与同余最短路的贴，那么先按照难度顺序，或者说技能树顺序来吧。
文末附上了我看过的所有帖子，基本来源于洛谷，如果其他人看到了这个学习记录，看我的感觉讲的不够清楚，没理解，请自行移步到这些原帖，一定是很容易懂的
P5960 【模板】差分约束
题意：
也就是给出n个数，然后这n个数有m个不等式，问满足要求的一组解。
思路：
本人太笨，一开始还觉得只要借助不等式算区间得值之类的就能做出来
1.想联想到最短路，转换成图论问题你必须要观察到 ，这个公式与最短路非常相似，不然是转换不到图论去的。能转换成图的关系就是，两个点之间的差值不能超过y1，如此一来，最短路就刚好适用，因为最短路可以提供两个点的间接关系，这是这道题的关键。
2.接下来要加入超级源点，因为不等式提供的是相对关系，你总得要一个具体的值对吧。但是不能是任意挑一个点，因为构建出来的图并不一定是连通图，设置所有的点与超级源点的路径为0
即，因为都是相对关系，所以不影响结果的得出，这样就联通了整个图，一次就可以了，
不过我觉得改成联通图独立判断应该也能行但是没啥必要。
3.接下来就是spfa的板子，推荐看D03 最短路 Bellman-Ford 算法 SPFA 算法——信息学奥赛算法_哔哩哔哩_bilibili
添边是不能双向边的，这并不是无向边，的关系只能得到单向边，如果你构建无向边（双向边），其实是创造了一个新关系。
这个图出现负环的情况是什么，负环其实就是,自己小于等于自己是错误的，很明显是NO答案。负环是指自身环无限更新至-∞的情况，并非有负边就是负环,其实负环就是互相要求对方在关系传递后一个比一个小，又要比对方大又要比对方小是冲突的。如果能保持稳定存在的关系，就不是NO
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define int128 __int128
#define endl '\n'
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int N = 2e5+10;
const int INF = 1e18;
const int MOD = 2023;int n,m;
vector<pair<int,int> > mp[N];
int vis[N];
int dis[N];
int cnt[N];bool spfa(int x){queue<int> q;vis[x]=1;dis[x]=0;q.push(x);while(q.size()){auto t=q.front();q.pop();vis[t]=0;for(auto [u,v] : mp[t]){if(dis[u]>dis[t]+v){dis[u]=dis[t]+v;if(vis[u]) continue;vis[u]=1;cnt[u]++;if(cnt[u]==n+1) return false;q.push(u);}}}return true;
}void solve(){cin >> n >> m;for(int i=0;i<m;i++){int x,y,c;cin >> x >> y >> c;mp[y].push_back({x,c});}for(int i=1;i<=n;i++){dis[i]=INF;mp[0].push_back({i,0});}if(!spfa(0)){cout << "NO" << endl;}else{for(int i=1;i<=n;i++){cout << dis[i] << " ";}}}signed main(){IOS;int t=1;
// cin >> t;while(t--){solve();}
}那么spfa用于判负环的最短路初步学习就到这了。
总结：数学关系能转换成最短路联系，因为最短路能保持着原有的传递关系，且spfa能解决负环问题。
P3403 跳楼机
题意：
思路：
1.这题先可以转换成给出3个数字操作，能得到哪些数字,但没有要求最小操作数。所以可以看成，任何一个新得到的数加上别的数能得到的数，现在我们假设得到了一个数字，它可以+a*k，也就是构成了一个类似于周期循环一样的，是不是代表一个数的相同余数的最小值被得到后，之后处于相同余数（每个周期的相同余数）的所有值都可以被得到？
这个思路可能并不好不适用所有人，该想法来自蓝桥杯的一道题，我当时并不会同余最短路……但是思路想到了同余最短路……P8646 [蓝桥杯 2017 省 AB] 包子凑数 题解 - 洛谷专栏如果感兴趣可以看这个。
2.现在明确如果知道一个同一个余数的最小值知道后，那么在这个相同余数下的所有以a构成循环的数之后一定能通过+a得到。那么问题转换成了，怎么求出每个%a的余数，最小的数是谁。
那么很明显最短路利用剩下的b，c得到就行了，(x+a)%a==x，a的使用是无意义的。
3.如果还用1的话，明显加大了代码实现的复杂度，不妨h--，然后转换成0到h-1的高度进行余数的计算就可以了。后面数字的计算其实就是(h-dis[x])/a+1，这个自己画个图或者想想应该能想明白吧？类似于还有多少个周期这样的意思。然后这道题可以不用spfa得到，因为没有负权，如此一来也不存在负环，可以用dij,其实都是一样的。
spfa代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define int128 __int128
#define endl '\n'
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int N = 2e5+10;
const int INF = 1e18;
const int MOD = 2023;int dis[N];
int vis[N];
int cnt[N];
vector<pair<int,int> > mp[N];bool spfa(int x,int a){queue<int> q;vis[x]=1;dis[x]=0;q.push(0);while(q.size()){auto t=q.front();q.pop();vis[t]=0;for(auto [u,v] : mp[t]){if(dis[u]>dis[t]+v){dis[u]=dis[t]+v;if(vis[u]) continue;vis[u]=1;cnt[u]++;q.push(u);}}}return true;
}void solve(){int h;cin >> h;h--;int a,b,c;cin >> a >> b >> c;for(int i=0;i<=a;i++){dis[i]=INF;mp[i].push_back({(i+b)%a,b});mp[i].push_back({(i+c)%a,c}); }spfa(0,a);int ans=0;for(int i=0;i<a;i++){if(dis[i]<=h){ans+=(h-dis[i])/a+1;}}cout << ans << endl;}signed main(){IOS;int t=1;
// cin >> t;while(t--){solve();}
}dij代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define int128 __int128
#define endl '\n'
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int N = 2e5+10;
const int INF = 1e18;
const int MOD = 2023;int dis[N];
int vis[N];void dij(int n,int b,int c){priority_queue<pair<int,int> ,vector<pair<int,int>> , greater<pair<int,int>> > q;dis[0]=0;q.push({0,0}); //点 最短路while(q.size()){auto [v,u]=q.top();q.pop();if(vis[u]) continue;vis[u]=1;int nex=(u+b)%n;if(dis[nex]>dis[u]+b){dis[nex]=dis[u]+b;q.push({dis[nex],nex});}nex=(u+c)%n;if(dis[nex]>dis[u]+c){dis[nex]=dis[u]+c;q.push({dis[nex],nex});}}
}void solve(){int h;cin >> h;h--;int a,b,c;cin >> a >> b >> c;for(int i=0;i<=a;i++){dis[i]=INF;}dij(a,b,c);int ans=0;for(int i=0;i<a;i++){if(dis[i]<=h){ans+=(h-dis[i])/a+1;}}cout << ans << endl;}signed main(){IOS;int t=1;
// cin >> t;while(t--){solve();}
}
