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];
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) return true;
if (!st[j]) {
st[j] = true;
q.push(j);
}
}
}
}
return false;}
六、Prim算法求最小生成树
无向图；图中可能存在重边和自环；边权可能为负数。
算法思想：更新到集合的最短距离dist
int state[N],pre[N],st[N],dist[N];
int res;
void prim(){
memset(dist,0x3f,sizeof dist);
dist[1] = 0;
for(int i=1;i<=n;i++){
int t=-1;
for(int j=1;j<=n;j++){
if(!st[j] && (t==-1||dist[t]>dist[j])){
t = j;
}
}
st[t] = 1;
res += dist[t];
for(int j=1;j<=n;j++){
if(!st[j] && dist[j]>g[j][t]){
dist[j] = g[j][t];
}
}
}}
七、Kruskal算法求最小生成树
算法思想：借助并查集优化算法
include <bits/stdc++.h>
using namespace std;
const int N = 100100;
const int M = 2*N; // 边的数量
struct edge{
int a;
int b;
int w;
bool operator <(const edge &x) const
{
return w<x.w;
}}egs[M];
int n,m;
int pre[N];
int find(int x){
if(pre[x]==x) return x;
else return pre[x] = find(pre[x]);}
int kreskal(){
int res = 0,cnt = 0;
for(int i=0;i<m;i++){
int a = egs[i].a, b = egs[i].b, w = egs[i].w;
if(find(a)!=find(b)){
pre[find(a)] = pre[find(b)];
cnt ++;
res += w;
}
}
if(cnt==n-1) return res;
else return 0x3f3f3f3f;}
int main()
{
scanf(<span data-raw-text="" "="" data-textnode-index-1653737321746="723" data-index-1653737321746="5432" class="character">"%d%d<span data-raw-text="" "="" data-textnode-index-1653737321746="723" data-index-1653737321746="5437" class="character">",&n,&m);
int a,b,c;
for(int i=1;i<=n;i++) pre[i] = i;
for(int i=0;i<m;i++){
scanf(<span data-raw-text="" "="" data-textnode-index-1653737321746="746" data-index-1653737321746="5542" class="character">"%d%d%d<span data-raw-text="" "="" data-textnode-index-1653737321746="746" data-index-1653737321746="5549" class="character">",&a,&b,&c);
egs[i] = {a,b,c};
}
sort(egs,egs+m);
int t = kreskal();
if(t==0x3f3f3f3f) cout << <span data-raw-text="" "="" data-textnode-index-1653737321746="764" data-index-1653737321746="5681" class="character">"impossible<span data-raw-text="" "="" data-textnode-index-1653737321746="764" data-index-1653737321746="5692" class="character">" << endl;
else cout << t << endl;
return 0;}
八、一点问题：
1、prim 和 dijkstra 的区别与联系：
（1）prim 为更新到集合的最短距离dist; 而dijkastra 为更新到源点的最短距离dist。即更新方式不同
（2）两者均可以使用优先队列优化.不过在优化时，prim最好采用kruskal优化.
2、spfa 和 dijkstra 的区别与联系：
（1）st数组的作用不同，可以将一个点反复设为0和1
（2）SPFA算法中使用的是队列，目的只是记录一下当前发生过更新的点；而dijkstra算法使用的是优先队列，目的是取出不在集合中的距离源点最近的点
3、求负环的常用方法：
求负环的常用方法，基于SPFA，一般都用方法 2：
方法 1：统计每个点入队的次数，如果某个点入队n次，则说明存在负环
方法 2：统计当前每个点的最短路中所包含的边数，如果某点的最短路所包含的边数大于等于n，则也说明存在负环
