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，则也说明存在负环