2024双学位课程-数据机构与算法-第四次机考

/*

使用优先队列实现Dijkstra
dist[MAXN]记录路径长度和

*/

void DijkstraPQ(int startv,int endw)
{
    int i,j,k,min;
    priority_queue<pathSum> pq;  //队列元素（pre，v，costSum）pre,以及通过pre到达v的路径长度
    bool s[MAXN]={false};
    for(i=1;i<=MAXN;i++) dist[i]=INF;

    //以“startv”作为源点，初始化S和dist数组,由于题目不要求记录路径所以不存pre
    dist[startv]=0;
    s[startv]=true;


    for(auto &e:edgeFrom[startv])  pq.push({e.u,e.v,e.cost});

    while(!pq.empty())
    {
        pathSum tmp=pq.top();
        pq.pop();

        if(tmp.v==endw)//已找到到达目的地的最短路
        {
            cout<<tmp.costSum<<endl;
            exit(0);
        }
        if (s[tmp.v]) continue;  //优先队列中的元素不能更新，所以可能有无效边
        /*
            出队的顶点tmp.v加入到最短路径树，检查所有从v出发的边，更新队列
        */
        s[tmp.v]=true;
        dist[tmp.v]=tmp.costSum;
        //cout<<"a path add into the shortest Tree: ("<<tmp.pre<<" "<<tmp.v<<" "<<tmp.costSum<<")"<<endl;

        for(auto &e:edgeFrom[tmp.v]) //,一条边，e（u，v, cost)
        {
            int w=e.v;
            if(!s[w]&&(dist[w]>tmp.costSum+e.cost))
            {
                dist[w]=tmp.costSum+e.cost;
                pq.push({tmp.v,w,dist[w]});
                /*  算法逻辑应该是：
                    if(pq contians w), update w to  {tmp.v,w,dist[w]} ;
                    else pq.insert({tmp.v,w,dist[w]});
                    由于优先队列不支持按w索引修改，所以都插入。pop时增加判断
                */

            }
        }
    }
    return;
}

void siftdown(int a[], int i, int n) 
{   int j,t;
    t=a[i];
    while ( (j=2*i+1)< n  )  //当i有子结点的时候才需要调整
     { //让j指向a[i]左子结点和右子结点（如果有）中键值较大的一个
        if (j<n-1  &&  a[j]<a[j+1] ) j++;
        if  (t < a[j]) //如果t比子结点小，不符合堆的定义
        {   a[i]=a[j];  //将较大的值放入根a[i]。
            //a[j]=t; //“交换”，因为还要继续向下调整，                   所以可省略a[j]=t的操作
            i=j;  //  结点a[j]作为新的将要调整的子树的根，                           }
         else break;//t不小于左右子结点，符合定义，终止循环
     }
     a[i]=t;    //若循环中省略，则循环终止后， t填入当前停止的结点
}


void swim(int a[], int k) 
//适用条件： a[k]是序列最后一个结点，之前的结点是一个堆。
//方法：由于a[k]比它的父结点大，破坏了堆，通过交换它和它的父结点来修复
{   
    while ( k>0 && a[(k-1)/2]< a[k]  ) 
     {      swap(a[(k-1)/2],a[k] ); 
                //将较大的值和它的父结点交换
            k= (k-1)/2;  
            //  结点k作为新的将要调整的结点
     }
}


void floyd(int n)
{   int i,j,k;
    for(i=1;i<=n;i++)   //读入有向边，为递推矩阵赋初值
      for(j=1;j<=n;j++)     {   a[i][j]=cost[i][j];
                    path[i][j]=0;    }
    //嵌套循环，递推求A（k）
    for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
               for(j=1;j<=n;j++)
            if(a[i][k]+a[k][j]<a[i][j])
                { a[i][j]=a[i][k]+a[k][j];
                  path[i][j]=k;
                }
}