【学习】最短路

堆优DJ

适用无负边权，跑稠密图，O((V+E)logV)。 $O ((V + E) l g V)$

struct node{
    int nxt,to,w;
}e[M];
int d[M],head[M];
bool vis[M];
typedef pair<int,int> P;
priority_queue<P,vector<P>,greater<P> >q;
while(!q.empty()){
    int u=q.top().second;q.pop();
    if(vis[u])continue;
    vis[u]=1;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].v;
        if(dis[v]>dis[u]+e[i].w){
            dis[v]=dis[u]+e[i].w;
            q.push(P(dis[v],v));
        }
    }
}

SPFA

可以跑负边权和判断负环，适合稀疏图，大概O(VE)，容易被卡。

Floyd

O(N*N*N)

inline void floyd(){
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(dist[i][k]+dist[k][j]<dist[i][j])
                    dist[i][j]=dist[i][k]+dist[k][j];
}