Bellman-ford(处理有负权边的图)
如果有负权回路 最短路不一定存在
for循环N次 (如果当前迭代k次，从1号点经过不超过K条边的最短路的距离)
（所以在第N次时 又更新了 ，说明存在一条最短路径大于N条边(n+1)个点 必有负环）
（说明bellman也可以求负环）
for所有边a,b,w（存在a到b的权重为w的边）
更新dist[b]=min(dist[b],dist[a]+w); （松弛操作）
（从一号点走到b和从a到b的距离哪个短）
循环完所有边:(dist[b]<=dist[a]+w)三角不等式
两重循环第一重n,第二重m，时间复杂度O(nm);
存边方式：邻接表，邻接矩阵或者结构体
struct{
a,b,w
}s[N];
负环不影响的情况:从1走到n 不经过负环
acwing 853有边数限制的最短路(最多经过 k 条边的最短距离)只能用bellman做
解释备份出现串联情况:
如果k=1 因为第二步遍历的是所有边 所以虽然k=1但是1->2->3能在一次k中（先枚举1->2再枚举2->3） 保证不出现串联就先用上一次迭代的结果 所以要备份
串联：由于这个算法的特性决定，每次更新得到的必然是在多考虑 1 条边之后能得到的全局的最短路。而串联指的是一次更新之后考虑了不止一条边：由于使用了松弛，某节点的当前最短路依赖于其所有入度的节点的最短路；假如在代码中使用dist[e.b]=min(dist[e.b],dist[e.a] + e.c);，我们无法保证dist[e.a]是否也在本次循环中被更新，如果被更新了，并且dist[e.b] > dist[e.a] + e.c，那么会造成当前节点在事实上“即考虑了一条从某个节点指向a的边，也考虑了a->b”，共两条边。而使用dist[e.b]=min(dist[e.b],last[e.a] + e.c);，可以保证a在dist更新后不影响对b的判定，因为后者使用last数组，保存着上一次循环中的dist的值。
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=510,M=10010;
int n,m,k;
int dist[N],backup[N];
struct edge{
int a,b,w;
}edges[M];
int bellman_ford(){
memset(dist,0x3f,sizeof(dist));
dist[1]=0;
for(int i=0;i<k;i++){
memcpy(backup,dist,sizeof(dist));//先备份,可能出现串联
for(int j=0;j<m;j++){
int a=edges[j].a,b=edges[j].b,w=edges[j].w;
dist[b]=min(dist[b],backup[a]+w);
}
}
if(dist[n]>0x3f3f3f3f/2)return 0x3f3f3f3f;//不直接写成dist[n]==0x3f3f3f3f 可能出现这种-2+INF的情况
return dist[n];//可能把正无穷更新为比正无穷小一点的数 减了也不能减太多 最多500*10000（题意）
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<m;i++){
int a,b,w;
scanf("%d%d%d",&a,&b,&w);
edges[i]={a,b,w};
}
int t=bellman_ford();
if(t==0x3f3f3f3f)puts("impossible");
else printf("%d\\n",t);
return 0;
}
关于这题的返回 可以将bellmen return后再判断（主函数中）
if (dist[n] > 0x3f3f3f3f / 2) puts("impossible");
else printf("%d\\n", dist[n]);
spfa算法(对bellman优化)(不要负权回路)
对于dist[b]=min(dist[b],dist[a]+w);做优化
只有a变小 dist[b]才变小
queue<-1;
while queue不空（队列里面存的都是变小的a，来以此更新后面的节点）
(1)t<-q.front;q.pop();
(2)更新一下t的所有出边t–w–>b;queue<-b(用更新过的点更新其他的点)
acwing 851
st数组比较好理解的解释:队列中有重复的点没有意义,因为前面假如出现了可以把二这个点变小的值，那就更新，但不用加入队列，因为队列里已经有二这个点了，他肯定会遍历到，然后去更新与他相邻的节点之间的距离，这样就提高了效率，而被淘汰的点之后又会被加入队列是因为此时他的最短距离又被更新了，那么自然和他相连的节点距离也会更新，所以需要把他重新加入队列之中
#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 ++ ;
}
int spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
queue<int> q;
q.push(1);
st[1] = true;//st数组存的是当前这个点是不是在队列当中 防止队列中存储重复的点
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 (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;
}
