dij
//二叉堆优化过的dij
#include <cmath>
#include <queue>
#include <string>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define forn(i, n) for (int i = 0; i < (n); i++)
#define forab(i, a, b) for (int i = (a); i <= (b); i++)
#define forba(i, b, a) for (int i = (b); i >= (a); i--)
#define mset(a, n) memset(a, n, sizeof(a))
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define P pair<int,int>
#define fi first
#define se second
using namespace std;
#define N 1000010
#define maxn 1005
#define inf 0x3f3f3f3f
#define ll long long
int head[N], ver[N], edge[N], Next[N], d[N];
int n, m, tot;
bool vis[N];
priority_queue<pair<int,int> > q; //first存的d[i]的相反数,这样就变成了小根堆
void addedge(int x,int y,int z)
{
ver[++tot] = y;
edge[tot] = z;
Next[tot] = head[x];
head[x] = tot;
}
void Init()
{
mset(head,0);
tot=0;
}
void dij()
{
mset(d,0x3f);
mset(vis,0);
d[1] = 0; //以1 为起始点,
q.push(make_pair(0, 1));
while(q.size())
{
int x = q.top().se;
q.pop();
if(vis[x])
continue;
vis[x] = 1;
for (int i = head[x]; i;i=Next[i])
{
int y = ver[i];
int z = edge[i];
if(d[y]>d[x]+z)
{
d[y] = d[x] + z; //更新
q.push(make_pair(-d[y], y));
}
}
}
}
int main()
{
fast;
cin >> n >> m;
forab(i,1,m)
{
int x, y, z;
cin >> x >> y >> z;
addedge(x, y, z);
//addedge(y,x,z); //无向边
}
dij();
forab(i, 1, n) cout << d[i] << endl; //单源最短路
system("pause");
}
SPFA
#include <cmath>
#include <queue>
#include <string>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define forn(i, n) for (int i = 0; i < (n); i++)
#define forab(i, a, b) for (int i = (a); i <= (b); i++)
#define forba(i, b, a) for (int i = (b); i >= (a); i--)
#define mset(a, n) memset(a, n, sizeof(a))
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define P pair<int,int>
#define fi first
#define se second
using namespace std;
#define N 1000010
#define maxn 1005
#define inf 0x3f3f3f3f
#define ll long long
int head[N], ver[N], edge[N], Next[N], d[N];
int n, m, tot;
bool vis[N];
int in[N]; //判负环可用
void addedge(int x,int y,int z)
{
ver[++tot] = y;
edge[tot] = z;
Next[tot] = head[x];
head[x] = tot;
}
void Init()
{
mset(head,0);
tot=0;
}
void spfa()
{
mset(d, 0x3f);
mset(vis, 0); //这里的vis跟dij的有所不同，spfa的vis是记录点是否在队列里面，所以要每次进出更新
d[1] = 0;
vis[1] = 1;
q.push(1);
while(q.size())
{
int x = q.front();
q.pop();
vis[x] = 0; //x出队列
for (int i = head[x]; i;i=Next[i])
{
int y = ver[i];
int z = edge[i];
if(d[y]>d[x]+z)
{
d[y] = d[x] + z;
if(!vis[y])
{
vis[y] = 1;
q.push(y);
}
}
}
}
}
int main()
{
fast;
cin >> n >> m;
forab(i,1,m)
{
int x, y, z;
cin >> x >> y >> z;
addedge(x, y, z);
//addedge(y, x, z); 无向边
}
spfa();
forab(i, 1, n) cout << d[i] << endl;
}
负环和差分约束
之前写程序设计作业的时候就了解过spfa和差分约束，这里再解释一下
负环： 一个边权和为复数的环称为负环。
不难知道，如果图中存在负环，那么无论经过多少次迭代，总存在有向边(x,y,z)使得
dist[y] > dist[x] + z则spfa算法无法结束。
根据抽屉原理（不懂自行百度，我记着小学奥数就讲过= =），若存在一个dist[x] 从起点1到节点x的最短路包含>=n条边，则这条路径必然重复经过的某个结点p，也就是说这条最短路上存在一个环，环上的每个点都能更新下一个点的dist，p绕环一圈最后可以更新他自己，因此，整个环的总长度为负数，每绕一圈总长度就会减少一点，越来越少，不可能收敛到每条边都满足三角不等式的状态。
因此 有以下方法判定法则（有了spfa就不用bellman-ford了吧，我是只看了spfa）
第一种 按照上段文章所写，设cnt[x] 表示从1到x的最短路径包含的边数，cnt[1] = 0，当执行dist[y] = dist[x] + z 时，同样更新cnt[y] = cnt[x] + 1,此时若有cnt[y] >=n 则存在负环，若正常结束算法，则没有负环
第二种 记录每个点的入队次数 次数达到n时则有负环，不过一般不如第一种的效率高。
差分约束 另一篇文章里面给过一些详细的证明这里就不写了。