Floyd

/*
来自王老师，Floyd在最下面
void dijkstra(){
    memset(d,0x3f,sizeof(d));
    d[s]=0;
    for(int i=1;i<=n;i++){
        int mi=-1;
        for(int j=1;j<=n;j++)
            if(!f[j]&&(mi==-1||d[j]<d[mi]))
                mi=j;
        f[mi]=true;
        for(int j=pre[mi];j!=0;j=a[j].next){
            int to=a[j].to;
            if(!f[to]&&d[mi]+a[j].len<d[to])
                d[to]=d[mi]+a[j].len;
        }
    }
}

SPFA: Shortest Path Fast Algorithm
1.求带负权的最短路
2.判断负环

q.push(s)
f[s]=true;
while(队列里有点){
    u=q.front();
    for(u所有连接的点v){
        //如果有更短的路
        if(d[u]+uv的边长<d[v]){
            //更新走到v点的最短路
            d[v]=d[u]+uv的边长
            //如果点v不在队列中
            if(f[v]==false){
                q.push(v);
                f[v]=true;
            }
        }
    }
    q.pop();
    f[u]=false;
}

Floyd(插点法)
d[i,j]=min(d[i,j],d[i,k]+d[k,j])


*/