应该有些理解偏差的地方还没有修改。反正现在只是随便水一下，等到专题写完再改吧

新的相关知识

1.链式前向星，用于存图

链式前向星（加快图的搜索）_早睡身体好_的博客-CSDN博客

int e[N],ne[N],w[N],h[N],idx;void add(int a,int b,int c){e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}遍历
for(int i = h[t];i != -1;i = ne[i]){int j = e[i];}
}

2.优先队列，

优先队列，默认从大到小排序
加greater从小到大
q.push时，push一个负数，就可以省下写从小到大优先队列的功夫

3.cout的参数设置

1）fixed和setpricision()在iomanip 库中
2）c++98的sqrt参数必须是double类型。

4.负环

负环详解 - 子谦。 - 博客园 (cnblogs.com)
图上的最短路都是确定的。但是一旦图上有一个负环，s�到t�的最短路就会不远千里的去覆盖上这个环（只要能够到达），并且不厌其烦的走上一遍又一遍。由于负环的边权和是负的，并且它是一个环，也就是说走一遍和走无数遍都停留在进入的那个点。那么最短路每经过一次这个负环，这个费用都会缩小一点，如果经过了无数次，也就是无穷小，也就是不存在最短路。
//当然这里有一个限定，就是每个点经过的次数不能超过1次。

应该就是用st数组来实现这个点。

在SPFA中，每个点最多被其他n−1个点各收紧一次，如果被收紧了n次，显然是不合理的。那么我们就记录每个点被收紧的次数，有任何点超过n次，就可以判定存在负环了，如果SPFA成功运行完了，就证明不存在负环。

cnt[j] >=- n 时

dijkstra

1.堆优化Dijkstra求最短路

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int,int> PII;
const int N = 2e5 + 10;
int e[N],ne[N],w[N],h[N],idx;
int d[N],st[N];
void add(int a,int b,int c){e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}
void dijkstra(){priority_queue<PII> q;q.push({0,1});d[1] = 0;while(q.size()){int t = q.top().second;q.pop();if(st[t] ) continue;st[t] = true;for(int i = h[t];i != -1;i = ne[i]){int j= e[i];if(d[j] > d[t] + w[i]){d[j] = d[t] + w[i];q.push({-d[j],j});}}}
}
void init(){idx = 0;memset(h,-1,sizeof h);memset(st,0,sizeof st);memset(d,0x3f,sizeof d);
}void solve(){init();int n,m;cin >> n >> m;for(int i =1;i <= m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c);}dijkstra();if(d[n] != 0x3f3f3f3f)cout << d[n] << endl;else cout << -1 << endl;
}
int main(){solve();return 0;
}

套路 图上一个点到其他点的最短路

前提：

图上一个点到其他点的最短路

情景

输出一个整数，表示 1 号点到 n 号点的最短距离。

应对：

与spfa区别：
1）起点不用特别设置bool值，结果发现spfa的起点设置bool完全是多余的
结果发现我的理解有偏差·，求负环时可以去掉起点bool设置，但求最短路不行
2）要用优先队列，greater或less然后push负数
3）元素出队不需要改bool值
4）在遍历链式前向星前判元素bool
5）判队中元素为true直接continue；false则设为true

2.堆优化silver cow party(正反向同时建图)

链接

Silver Cow Party

代码

题解代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>#define MAXN 1010
#define MAXM 200010using namespace std;typedef long long ll;
typedef pair<int,int> PII;const int inf=0x3f3f3f3f;int n,m,x;int head[2][MAXN],ed[MAXM],nex[MAXM],val[MAXM],idx;
h，e，ne，w，id
int dist[2][MAXN];int vis[MAXN];
写成二维，保存两种建图的数据
void add(int op,int a,int b,int c)
{ed[idx]=b;val[idx]=c;nex[idx]=head[op][a];head[op][a]=idx++;因为是用a来哈希访问到idx，所以idx值怎么样根本无所谓
}
void dijkstra(int start,int op)
{两种dijkstra的起点不同，通过传入参数来解决。memset(dist[op],0x3f,sizeof(dist[op]));二维数组只初始化一维。没必要，但没学过写来看看memset(vis,0,sizeof(vis));priority_queue<PII > q;q.push({0,start});dist[op][start]=0;while(q.size()>0){PII temp=q.top();q.pop();int temp_dis=temp.first,temp_pos=temp.second;if(vis[temp_pos]==1)continue;vis[temp_pos]=1;for(int i=head[op][temp_pos];i!=-1;i=nex[i]){int j=ed[i];if(vis[j]==1)continue;if(dist[op][j]>dist[op][temp_pos]+val[i]){dist[op][j]=dist[op][temp_pos]+val[i];q.push({-dist[op][j],j});}谜之操作，直接让temp存q.top().second就好了。}        }
}int main()
{// ios::sync_with_stdio(false);// cin.tie(0),cout.tie(0);cin >> n >> m >> x;memset(head,-1,sizeof(head));for(int i=1;i<=m;i++){int a,b,c;cin >> a >> b >> c;add(0,a,b,c);//正向建边(求终点到每个点的距离)——回家add(1,b,a,c);//反向建边(求每个点到终点的距离)——启程}dijkstra(x,0);dijkstra(x,1);谜之操作，一个把op写前面，一个把op写后面。int res=0;for(int i=1;i<=n;i++)res=max(res,dist[0][i]+dist[1][i]);
找最大cout << res << endl;return 0;
}

模仿

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int,int> PII;
const int N =1e6 + 10;
int h[2][N],e[N],ne[N],w[N],idx;
int d[2][N],st[N];
void add(int op,int a,int b,int c){e[idx] = b,w[idx] = c,ne[idx] = h[op][a] ,h[op][a] = idx++;
}
void dijkstra(int op,int s){memset(d[op],0x3f,sizeof d[op]);memset(st,0,sizeof st);priority_queue<PII> q;q.push(make_pair(0,s));未知起点变为sd[op][s] = 0;while(q.size()){int t = q.top().second;q.pop();if(st[t] ) continue;st[t] = true;for(int i = h[op][t];i != -1;i = ne[i]){int j = e[i];if(d[op][j] > d[op][t] + w[i]){d[op][j] = d[op][t] + w[i];q.push(make_pair(-d[op][j],j));}}}
}
int main(){int n,m,ed;memset(h,-1,sizeof h);cin >> n >> m >> ed;for(int i = 1;i <= m;i++){int a,b,c;cin >> a >> b >> c;add(0,a,b,c);add(1,b,a,c);}dijkstra(0,ed);dijkstra(1,ed);int res= 0;for(int i = 1;i <= n;i++){res = max(res,d[0][i] + d[1][i]);}cout << res << endl;return 0;
}

套路 求有向图上点到一个点的来回的最短路

如果是无向图就直接最短路 * 2
但是有向图，需要分开求来与回的两段最短路

前提：求有向图上点到一个点的来回的最短路。

应对

朴素做法，求出图上点到n的最短路，然后再求n到图上点的最短路，后一步需要n次dijkstra，复杂度很高。所以需要变化

实际做法正向建图之后再反向建图，用一个二维数组来保存两个图，通过一个op来区分两个图的add和dijkstra

具体点就是把h，d，add，dijkstra变成二维。

情景

N 头牛要去参加在某农场举行的一场编号为 X 的牛的派对。

有 M 条有向道路，每条路长 Ti；每头牛参加完派对后都必须回到家，每头牛都会选择最短路径。

求这 N 头牛的最短路径（一个来回）中最长的一条的长度。

习题1.堆优化Til the Cows Come Home（1的同类）

套路

前提：

图上其他点到一个点的最短距离

情景

Bessie从地标N到地标1所必须走的最小距离。
终点是地标1，N代表图上其他点。

所以dijkstra的初始点设为1.

代码

题解代码

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<string>
#define R register int
using namespace std;
const int manx=1e4+5;
int head[manx],d[manx];
bool vis[manx];
int n,m,k=0,s,e;
struct node{int v,next,w;
}a[manx];
void add(int u,int v,int w)
{a[++k].next=head[u];a[k].w=w;a[k].v=v;head[u]=k;
}
void dij()
{memset(d,0x3f,sizeof(d));memset(vis,0,sizeof(vis));d[s]=0;priority_queue<pair<int,int> >q;q.push(make_pair(0,s));while(q.size()){int u=q.top().second;q.pop();if(vis[u]) continue;vis[u]=1;for(int i=head[u];i;i=a[i].next){int v=a[i].v,w=a[i].w;if(d[v]>d[u]+w) d[v]=d[u]+w,q.push(make_pair(-d[v],v));}}}
int main()
{scanf("%d%d",&m,&n);e=1,s=n;反向建图，仍以1为流程起点for(int i=1;i<=m;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);add(u,v,w);add(v,u,w);无向边建图}dij();cout<<d[e];return 0;
}

模仿

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int,int> PII;
const int N = 2e5 + 10;
int e[N],ne[N],w[N],h[N],idx;
int d[N],st[N];
void add(int a,int b,int c){e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}
void dijkstra(){priority_queue<PII> q;q.push({0,1});d[1] = 0;while(q.size()){int t = q.top().second;q.pop();if(st[t] ) continue;st[t] = true;for(int i = h[t];i != -1;i = ne[i]){int j= e[i];if(d[j] > d[t] + w[i]){d[j] = d[t] + w[i];q.push({-d[j],j});q里的d[j],只决定j在何时被读取到，只是决定了顺序，所以全员变成-数，然后再从小到大排序的效果等价于原来的从大到小排序}}}
}
void init(){idx = 0;memset(h,-1,sizeof h);memset(st,0,sizeof st);memset(d,0x3f,sizeof d);
}void solve(){init();int n,m;cin >> n >> m;for(int i =1;i <= m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c);}dijkstra();if(d[n] != 0x3f3f3f3f)cout << d[n] << endl;else cout << -1 << endl;
}
int main(){solve();return 0;
}

spfa

前提条件

可能有负权边，判断负环

应对，与dijkstra区别

与堆优化dijkstra相像，
区别在于
1）元素出队时要判false，
2）st[j]要在dist[j] 需要更新时才判，如果false要true然后入队
3）起点要设为true ，多余。

1.spfa求最短路

AcWing 851. spfa求最短路 - AcWing

代码

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>using namespace std;const int N = 100010;int n, m;
int h[N], w[N], e[N], ne[N], 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 ++ ;链式前向星idx边的数量e第idx条边的终点w第idx条边的权值ne第idx条边的h[a]与当前边起点相同的上一条边的编号h[a]起点为a的边的编号。}
存一条起点a，终点b，边权c的边；
add1 2 1
add2 3 1
add3 1 1
e[] = {2,1,3,2,1,3};
w[] = {1,1,1,1,1,1};
ne[] = {h[1]=0,h[2]=0,h[2]=2,h[3]=0,h[3]=4,h[1]=1}
idx 2 ,h[1] = 1 
idx 3 ,h[2] = 2
idx 4 ,h[2] = 3;
idx 5 ,h[3] = 4;
idx 6 ,h[3] = 3;
idx 7 ,h[1] = 6;
int spfa()
{memset(dist, 0x3f, sizeof dist);dist[1] = 0;起点初始化为0，其余正无穷。queue<int> q;q.push(1);while (q.size()){int t = q.front();q.pop();for (int i = h[t]; i != -1; i = ne[i]){初始值是起点为t的边的编号i = ne[i],获得起点为t的边下一条边的编号。int j = e[i];j = e[i],起点为t的边对应的终点if (dist[j] > dist[t] + w[i])找到更小走法，更新{dist[j] = dist[t] + w[i];意义不明if (!st[j]){q.push(j);st[j] = true;}}}}return dist[n];
}int main()
{scanf("%d%d", &n, &m);memset(h, -1, sizeof h);while (m -- ){int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c);}int t = spfa();if (t == 0x3f3f3f3f) puts("impossible");else printf("%d\\n", t);return 0;
}

例题2青蛙 给点建图，最大边的最小值

AcWing 4240. 青蛙 - AcWing

注意

fixed和setpricision()在iomanip 库中
c++98的sqrt参数必须是double类型。

代码

题解代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y secondconst int N = 4e4+10;
用点建无向图需要 n*n*2次，
PII p[N];
存点
因为题目只给了点，没有给边，要存点坐标
int e[N],ne[N],w[N],h[N],idx;
bool st[N];
int d[N];int getlen(PII a,PII b)
{return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);存的时候存平方式，输出时再开根。
}
void add(int a, int b, int c)  // 添加一条边a->b，边权为c
{e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;编号idx终点，编号idx边权，编号idx下一条边编号，哈希，起点a边编号
}void spfa()
{memset(st, false, sizeof st);memset(d,0x3f,sizeof d);dist数组，点到起点距离queue<int> q;q.push(1);st[1] = true;d[1] = 0;while(q.size()){int t = q.front();q.pop();st[t] = false;for(int i = h[t];i!=-1;i=ne[i]){int j = e[i];if(d[j] > max(d[t],w[i]))为什么取最大值未知{d[j] = max(d[t],w[i]);if(!st[j]){q.push(j);st[j] = true;}}}}
}int main()
{int n;int t = 1;while(true){cin>>n;if(n == 0) break;多组输入idx = 0;初始化idxfor(int i = 1;i<=n;i++){int x,y;cin>>x>>y;p[i] = {x,y};}memset(h, -1, sizeof h);for(int i =1;i<n;i++)for(int j = i+1;j<=n;j++){int w = getlen(p[i],p[j]);PII数组输入点得到权值拼平方add(i,j,w);add(j,i,w);}建图spfa();cout<<"Scenario #"<<t<<endl;cout<<"Frog Distance = "<<fixed<<setprecision(3) <<(double)sqrt((double)d[2])<<endl;取消cout的科学计数法，设置保留位数补充：cout会四舍五入。cout<<endl;t++;}
}作者：sklit8
链接：https://www.acwing.com/solution/content/106663/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

模仿代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <iomanip>
#include <cmath>
using namespace std;
typedef pair<int,int> PII;
#define x first
#define y second
const int N = 4e4 + 10;
排列型枚举点，大约枚举n*n/2次，乘2就是n*n
PII p[N];
int e[N],ne[N],w[N],h[N],idx;
bool st[N];
int d[N];
int getlen(PII a,PII b){return (a.x - b.x) * (a.x - b.x) + (a.y - b.y ) * (a.y - b.y) ;
}
void add(int a,int b,int c){e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}
void spfa(){memset(st,false,sizeof st);memset(d,0x3f,sizeof d);queue<int> q;q.push(1);st[1] = true;d[1] = 0;while(q.size()){int t = q.front();q.pop();st[t] = false;for(int i = h[t];i != -1;i = ne[i]){int j = e[i];if(d[j] > max(d[t],w[i])){d[j] = max(d[t],w[i]);if(!st[j]){q.push(j);st[j] = true;}}}}}
int main(){int n;int t = 1;while(cin >> n && n){idx = 0;数组开得够小，但sg f，这次是重复定义变量初始化边数for(int i = 1;i <= n;i++){int x,y;cin >> x >> y;p[i] = {x,y};}读入PII point数组memset(h,-1,sizeof h);初始化上一个起点为a的边对应的编号for(int i  = 1;i < n;i++){for(int j = i+1;j <= n;j++){int w = getlen(p[i],p[j]);add(i,j,w);add(j,i,w);用下标可以访问点，所以直接用下标建图}}组合型枚举建图spfa();cout << "Scenario #" << t++ << endl;cout << "Frog Distance = " << fixed << setprecision(3) <<sqrt(d[2]) << endl;cout << endl;}
}

卡壳点：

st[t]= false 写成了 t = false
结果一直输出 0 -》 忘记调用spfa
数组开得够小，但sg f，这次是重复定义用作下标的变量

套路

1）只给点建图

排列型枚举建图
自己计算边权。
可以保存长度平方，最后再sqrt然后输出

2）前提条件 a至b路径中最长边的最小值

情景

第一个石头上的青蛙要到第二个石头上找另一个青蛙玩耍。

给定a与b

这只青蛙希望，它的跳跃过程中，单次跳跃的最长距离尽可能短。
请你计算并输出这个最长距离的最小可能值

要找出最小可能值，首先要先把最长距离全部找出来。
所以题目的意思是找所有路径中最长边的最小值

应对

1.因为要取max，所以起点dist 设为 -0x3f3f3f3f，保证第一次的max(d[t],w[i]) 会得到w[i]的值
2.遍历链式前向星时,d[j] 取min(d[j],max(d[t],w[i]))

if(d[j] > max(d[t],w[i]))d[j] = max(d[t],w[i]);

3.dist数组值初始化为0x3f3f3f3f
为了保证d[j] 没更新过时，一定会被更新，所以要初始化为0x3f3f3f3f

memset(d,0x3f,sizeof d);

3）无向边建图：

得到一条无向边，要把起点终点add一次，调换后再add一次

例题3货物运输，最小边的最大值

AcWing 4241. 货物运输 - AcWing

代码

题解代码（解析）

#include<bits/stdc++.h>
using namespace std;
#define int long longconst int N=1010,M=N*N;
剩空间的开发，感觉没必要
int h[N],ne[M],e[M],w[M],idx;void add(int a,int b,int c)
{e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;链式前向星的加边操作
}int dis[M],st[M],n,m;
dist与bool st，点与边数量
typedef pair<int,int> PII;void spfa()
{queue<int> q;dis[1]=0x3f3f3f3f;q.push(1);st[1]=1;while(q.size()){auto t=q.front();谜之autoq.pop();st[t]=0;for(int i=h[t];i!=-1;i=ne[i]){链式前向星的遍历int j=e[i];if(dis[j]<min(dis[t],w[i])){dis[j]=min(dis[t],w[i]);if(!st[j]){st[j]=1;q.push(j);}}}}
}void init()
{idx=0;memset(h,-1,sizeof h);memset(dis,-0x3f,sizeof dis); memset(st,0,sizeof st);偏好此种写法，适合检查否则容易漏初始化
}void solve()
{init();谜之llscanf("%lld %lld",&n,&m);while(m--){int a,b,c;scanf("%lld %lld %lld",&a,&b,&c);add(a,b,c);add(b,a,c);}spfa();printf("%lld\\n\\n",dis[n]);
}
signed main()
{int t;   scanf("%lld",&t);for(int i=1;i<=t;i++){printf("Scenario #%d:\\n",i);solve();}return 0;
}//作者：天后
//链接：https://www.acwing.com/solution/content/129977/
//来源：AcWing
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

太多谜点，稍微修改下

#include<bits/stdc++.h>
using namespace std;
const int N=1010,M=N*N;
int h[N],ne[M],e[M],w[M],idx;
void add(int a,int b,int c)
{e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;   
}
int dis[M],st[M],n,m;
void spfa()
{queue<int> q;dis[1]=0x3f3f3f3f;q.push(1);st[1]=1;while(q.size()){int t=q.front();q.pop();st[t]=0;for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];if(dis[j]<min(dis[t],w[i])){dis[j]=min(dis[t],w[i]);if(!st[j]){st[j]=1;q.push(j);}}}}
}void init()
{idx=0;memset(h,-1,sizeof h);memset(dis,-0x3f,sizeof dis); memset(st,0,sizeof st);}void solve()
{init();scanf("%d %d",&n,&m);while(m--){int a,b,c;scanf("%d %d %d",&a,&b,&c);add(a,b,c);add(b,a,c);}spfa();printf("%d\\n\\n",dis[n]);
}
int main()
{int t;   scanf("%d",&t);for(int i=1;i<=t;i++){printf("Scenario #%d:\\n",i);solve();}return 0;
}//作者：天后
//链接：https://www.acwing.com/solution/content/129977/
//来源：AcWing
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

模仿代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e6 + 10;
int ne[N],e[N],w[N],h[N],idx;
int st[N],d[N];
void add(int a,int b,int c){e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}
void spfa(){queue<int> q;q.push(1);st[1] = 1;d[1] = 0x3f3f3f3f;while(q.size()){int t = q.front();q.pop();st[t]= 0;for(int i = h[t];i != -1;i = ne[i]){int j = e[i];if(d[j] < min(d[t],w[i])){d[j] = min(d[t],w[i]);if(!st[j]){st[j] = true;q.push(j);}}}}
}
void init(){memset(h,-1,sizeof h);memset(st,0,sizeof st);memset(d,-0x3f,sizeof d);idx = 0;
}
void solve(){init();int n,m;scanf("%d%d",&n,&m);for(int i = 1;i <= m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c),add(b,a,c);}spfa();cout << d[n] << endl << endl;
}int main(){int t;cin >> t;for(int i = 1;i <= t;i++){printf("Scenario #%d:\\n",i);solve();}return 0;
}

卡壳点

忘记调用init
d[j]写成st[j];
卡cin: 1e6的边，需要scanf

seg def读边时写成读点，nm弄混

套路

1）a至b路径中最小边的最大值

情景

现在，要从点 1 到点 n 运货。
已知每条边的最大承重，请你计算一次最多可以运多少货物。

每行三个整数 a,b,c，表示点 a 和点 b 之间有一条无向边，最大承重为 c。

应对：

1.因为要取min，所以起点dist 设为 正无穷0x3f3f3f3f，保证第一次的min(d[t],w[i]) 会得到w[i]的值
2.遍历链式前向星时，d[j] 取max(d[j],min(d[t],w[i]))，与上一道例题相反

if(d[j] < min(d[t],w[i]))d[j] = min(d[t],w[i]);

3.dist数组值初始化为-0x3f3f3f3f
为了保证d[j] 没更新过时，一定会被更新，所以要初始化为-0x3f3f3f3f,与上一题相反。

memset(d,-0x3f,sizeof d);

例题4 货币交换，spfa判负环

AcWing 4242. 货币兑换 - AcWing

代码

题解代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>#define MAXN 110using namespace std;typedef long long ll;
typedef pair<double,double> PDD;
题目给的浮点数据，用double存
//const double eps=1e-8;
莫名奇妙的东西int n,m,start;double money;
int head[MAXN],ed[2*MAXN],nex[2*MAXN],idx;
PDD val[2*MAXN];double dist[MAXN];
int vis[MAXN],cnt[MAXN];void add(int a,int b,PDD c)
{ed[idx]=b;val[idx]=c;nex[idx]=head[a];head[a]=idx++;
}int spfa()
{queue<int> q;q.push(start);vis[start]=1;while(q.size()){int temp=q.front();q.pop();vis[temp]=0;for(int i=head[temp];i!=-1;i=nex[i]){double rate=val[i].first,cost=val[i].second;int j=ed[i];//if(dist[j]+eps<(dist[temp]-cost)*rate)if(dist[j]<(dist[temp]-cost)*rate){存价钱。如果有负环·就等于有正环dist[j]=(dist[temp]-cost)*rate;cnt[j]=cnt[temp]+1;存j的最短路经过了几条边。if(cnt[j]>=n)return 1;spfa判负环这里的语句看着是判持续增长的环if(vis[j]==0){vis[j]=1;q.push(j);}}   }}return 0;
}int main()
{// ios::sync_with_stdio(false);// cin.tie(0),cout.tie(0);cin >> n >> m >> start >> money;货币种类，兑换点数量，初始种类，初始数量。memset(head,-1,sizeof(head));memset(dist,-0x3f,sizeof(dist));double的初始化也用0x3ffor(int i=1;i<=m;i++){int a,b;double rate1,rate2,cost1,cost2;兑换率，服务费cin >> a >> b >> rate1 >> cost1 >> rate2 >> cost2;add(a,b,make_pair(rate1,cost1));add(b,a,make_pair(rate2,cost2));}dist[start]=money;if(spfa()==1)cout << "YES" << endl;else cout << "NO" << endl;return 0;
}

卡壳点，

没注意链式前向星数组要开二倍N

模仿代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N = 2e2 + 10;
typedef pair<double,double> PDD;
int n,m,stat;
PDD w[N];
bool st[N];
int cnt[N];
double d[N];double num;
int h[N],ne[N],e[N],idx;
void add(int a,int b,PDD c){e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}
int spfa(){queue<int> q;q.push(stat);st[stat] = 1;d[stat] = num;while(q.size()){int t = q.front();q.pop();st[t] = false;for(int i = h[t];i != -1;i = ne[i]){int j = e[i];double rate = w[i].first,cost = w[i].second;if(d[j] < (d[t] - cost) * rate){负环，小于时更新。d[j] = (d[t] - cost) * rate;cnt[j] = cnt[t] + 1;if(cnt[j] >= n){return 1;}if(!st[j]){st[j] = true;q.push(j);}}}}return 0;
}
int main(){cin >> n >> m >> stat >> num;memset(h,-1,sizeof h);//memset(d,-0x3f,sizeof d);判负环不需要初始化distfor(int i= 1;i <= m;i++){int a,b;double r1,r2,c1,c2;cin >> a >> b >> r1 >> c1 >> r2 >> c2 ;add(a,b,make_pair(r1,c1));add(b,a,make_pair(r2,c2));}if(spfa() == 1){cout << "YES" << endl;}else cout << "NO" << endl;return 0;
}

卡壳点

add时b写成a
变量重复定义
忘记初始化h

套路

情景

他想要通过先将自己手中的钱进行辗转兑换，最终再次换回 S� 货币的方式，让自己手中的钱变得更多。

与spfa联系

cnt d[j],dist,bool spfa
在spfa基础上，是用cnt数组来维护当前点最短路经过的边数量，与点数比较判断是否成环。
dist初始值无要求，可以不用初始化
d[j]更新变为取max
cnt
spfa作为bool函数返回1或0；

例题5 虫洞 spfa 判负环

AcWing 904. $kuangbin\_4.5虫洞(最短路练习)$ - AcWing

代码

题解代码

模仿前先批处理一下会好很多。

#include<cstring>
#include<algorithm>
#include<queue>
#include <iostream>using namespace std;
const int N = 6e3 + 10;
int n,m,k;int h[N],e[N],ne[N],w[N],idx;int st[N],cnt[N];
环计数组
int d[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(st,0,sizeof(st));memset(cnt,0,sizeof(cnt));memset(d,0,sizeof(d));多组输入要初始化。queue<int> q;for(int i=1;i<=n;i++){q.push(i);st[i]=1;}所有点都可作为起点。while(q.size()){int t=q.front();q.pop();st[t]=0;for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];if(d[j]>d[t]+w[i])这里又变成取min了。应该是判正环还是负环的关键。取min判负环取max判正环{d[j]=d[t]+w[i];cnt[j]=cnt[t]+1;if(cnt[j]>=n)return 1;if(st[j]==0){q.push(j);st[j]=1;}}}}return 0;
}int main()
{// ios::sync_with_stdio(false);// cin.tie(0),cout.tie(0);int T;cin >> T;while(T--){memset(h,-1,sizeof(h));h和idx一定要在add前初始化idx=0;cin >> n >> m >> k;点，路，虫洞for(int i=1;i<=m;i++)//双向路径{int a,b,c;cin >> a >> b >> c;add(a,b,c),add(b,a,c);}for(int i=1;i<=k;i++)//单向虫洞{int a,b,c;cin >> a >> b >> c;add(a,b,-c);回溯所以负权。}if(spfa()==1)cout << "YES" << endl;else cout << "NO" << endl;}return 0;
}

模仿代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 6e3 + 10;
int n,m,k;
int ne[N],e[N],w[N],h[N],idx;
int st[N],cnt[N],d[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(st,0,sizeof st);memset(cnt,0,sizeof cnt);memset(d,0,sizeof d);queue<int> q;for(int i= 1;i <= n;i++){q.push(i);st[i] = 1;求最短路的话，去掉st会变慢。但求最短路的话会直接tle，所以还是不要去掉比较好。}while(q.size()){int t = q.front();q.pop();st[t] = 0;for(int i = h[t];i != -1;i = ne[i]){int j = e[i];if(d[j] > d[t] + w[i]){d[j] = d[t] + w[i];cnt[j] = cnt[t] + 1;if(cnt[j] >= n){return 1;}if(st[j] == 0){q.push(j);st[j] = 1;}}}}return 0;}
int main(){int T;cin >> T;while(T--){memset(h,-1,sizeof h);idx = 0;cin >> n >> m >> k;for(int i = 1;i <= m;i++){int a,b,c;cin >> a >> b >> c;add(a,b,c),add(b,a,c);}for(int i = 1;i <= k;i++){int a,b,c;cin >> a >> b >> c;add(a,b,-c);}if(spfa()) cout << "YES" << endl;else cout << "NO" << endl;}return 0;
}

套路：无固定起点时的负环判断：

前提条件 任何点都可以做起点和终点

情景

现在农夫约翰希望能够从农场中的某片田地出发，经过一些路径和虫洞回到过去，并在他的出发时刻之前赶到他的出发地。

应对：

在spfa开始时，把所有点都作为起点处理一次。

例题6 Extended Traffic 判负环+求最短路

因为不理解负环所以在这题代码上花了点时间
负环详解 - 子谦。 - 博客园 (cnblogs.com)

代码

题解代码

// #include<bits/stdc++.h>
#include<cmath>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#define R register int
#define mm make_pair
#define inf 0x3f3f3f3f
using namespace std;
const int manx=1e3+5;
const int mamx=1e6+5;
struct node{int v,next,w;
}a[mamx];
int d[manx],head[manx],f[manx],ff[manx];
bool vis[manx];
int n,m,s,e,k=0;
void add(int u,int v,int w)
{a[++k].next=head[u];head[u]=k;a[k].v=v;a[k].w=w;
}
void spfa()
{memset(ff,0,sizeof(ff));memset(d,inf,sizeof(d));memset(vis,0,sizeof(vis));queue<int>q;d[1]=0;ff[1]=1;q.push(1);while(q.size()){int u=q.front();q.pop();vis[u]=0;for(int i=head[u];i;i=a[i].next){int v=a[i].v,w=a[i].w;if(d[v]>d[u]+w){d[v]=d[u]+w;if(!vis[v]&&ff[v]<=n){ //当ff[v]入队次数不大于n才进入if里面ff[v]++;q.push(v);vis[v]=1;}}}}
}
int main()
{int o,oo=1;cin>>o;while(o--){memset(head,0,sizeof(head));k=0;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&f[i]);scanf("%d",&m);for(int i=1;i<=m;i++){int u,v,w;scanf("%d%d",&u,&v);w=int(pow(f[v]-f[u],3));add(u,v,w);}spfa();scanf("%d",&s);printf("Case %d:\\n",oo++);while(s--){scanf("%d",&e);if(ff[e]>n||d[e]<3||d[e]==inf) printf("?\\n");else printf("%d\\n",d[e]);}}return 0;
}

改造代码

// #include<bits/stdc++.h>
#include<cmath>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
using namespace std;
const int N=1e6+5;int d[N],h[N],f[N],cnt[N];
bool st[N];
int n,m,s,ed,idx=0;
int w[N],ne[N],e[N];
void add(int a,int b,int c){e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}
void spfa()
{memset(cnt,0,sizeof cnt);memset(d,0x3f,sizeof d);这题不仅要判负环，还要找最短路，所以dist要初始化成有意义的值。找最短路要初始化成0x3f，然后起点0;,memset(st,0,sizeof st);queue<int>q;q.push(1);d[1] = 0;不能初始化为-0x3f3f3f3f,因为第一次更新是要把d[j]变成w[i],但表达式是d[t] + w[i],所以起点要是0。while(q.size()){int t=q.front();q.pop();st[t]=0;for(int i=h[t];i != -1;i = ne[i]){int j=e[i];if(d[j]>d[t]+w[i]){更新最小值，所以要取mind[j]=d[t]+w[i];if(cnt[j] >= n) continue;为什么是> n，不理解.总算想明白了，脑瘫作者把起点cnt初始化为1了如果cnt[t] >= n,说明存在负环，此时负环中的点可以不断更新，不存在最小值，所以要停止更新。cnt[j] = cnt[t] + 1;if(!st[j]){ q.push(j);st[j]=1;}}}}
}
int main()
{int T,oo=1;cin>>T;while(T--){memset(h,-1,sizeof(h));idx=0;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&f[i]);scanf("%d",&m);for(int i=1;i<=m;i++){int a,b,c;scanf("%d%d",&a,&b);c=pow(f[b]-f[a],3);add(a,b,c);}spfa();scanf("%d",&s);printf("Case %d:\\n",oo++);while(s--){scanf("%d",&ed);if(cnt[ed]>=n||d[ed]<3||d[ed]==0x3f3f3f3f) printf("?\\n");无法到达或没有最小值else printf("%d\\n",d[ed]);}}return 0;
}

卡壳点：

之前总结的负环d数组与起点初始化套路有点问题，如果要求最短路的话，dist和起点要照常初始化