最短路算法

//邻接表存储
int node[N];

struct Edge{
int to,next,value;
}edges[M];

int flag;

//矩阵存储
int dis[N][N];

int dis[N],vis[N];

priority_queueint> q;

//example:最短路径
int dis[N],vis[N];
priority_queueint,int>> q;

void dijsktra(int a){
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    
    dis[a]=0;
    q.push(make_pair(0,a));

    while (!q.empty()){
        int nn=q.top().second;
        q.pop();
        if (vis[nn]) continue;
        vis[nn]=1;
        for (int e=node[nn];e;e=edges[e].next){
            int ns=edges[e].to,value=dis[nn]+edges[e].value;
            if (valuedis[ns]){
                dis[ns]=value;
                q.push(make_pair(-dis[ns],ns));
            }
        }
    }
}

int dis[N],vis[N];
queueint> q;

void sfpa(int start){
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    
    //init
    dis[start]=0;
    vis[start]=1;
    q.push(start);
    
    while(!q.empty()){
        int cn=q.front();
        q.pop();
        vis[cn]=0;
        for(int e=node[cn];e;e=edges[e].next){
            int sn=edges[e].to,value=edges[e].value;
            if(dis[sn]>dis[cn]+value){
                dis[sn]=dis[cn]+value;
                if(!vis[sn])q.push(sn),vis[sn]=1;
            }
        }
    }
}

void floyd(int n){
    for(int k=1;k)//k指的是路径中包含前k个点
       for(int i=1;i)
           for(int j=1;j)
               dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}