图论专题模板

最短路

单源最短路

堆维护版本，复杂度 $O(nlogn)$

//s为源点
//node记录u到s的距离为dis
//dis[]记录到源点距离
//vis记录是否访问
//e[]记录边集
struct node{
    int u,dis;
    bool operator<(const node &t)const{return dis>t.dis;}
    //默认大顶堆，修改后是小顶堆
};
const int maxn=2000;
int n,m;
int dis[maxn];
int vis[maxn];
priority_queue<node>q;//优先队列维护
vector<int>e[maxn];
void dijkstra(int s){//起始点
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));//距离初始为无穷
    q.push({s,0});
    dis[s]=0;
    while(!q.empty()){
        int u=q.top().u;q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(auto v:e[u]){
            if(dis[v]>dis[u]+1){
                dis[v]=dis[u]+1;
                q.push({v,dis[v]});
            }
        }
    }
}