c++ - 如何减少 priority_queue ,greater> 中特定边的键，试图实现 prim 的算法？

Question

#include <bits/stdc++.h>
 using namespace std;

#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define LL long long int
#define pb push_back
#define mp make_pair
#define PI pair<int,int>
#define PL pair<LL,LL>
#define PIS pair< int,string>


#define test int t;cin>>t;while(t--)
#define ff first
#define ss second
#define INF 1000000000
#define input(a,n) for(i=1;i<=n;i++)cin>>a[i];
#define output(a,n) for(i=1;i<=n;i++)cout<<a[i]<<" ";
vector< vector<LL> >v(3002, vector<LL>(3002,-1));
priority_queue<PI, vector<PI> ,greater<PI> > pp;
LL w=0;
int vis[3002]={0};
/*void deck(int a ,int b, int *k)
{
    while(!pp.empty())
    {
        i=pp.top.ss;
        if(i==a)
          pp.top
    }
}*/
void prim(LL s, LL *k, LL *p,LL n)
{

    pp.push(mp(0,s));
    k[s]=0;
    LL i,x,a,b,c=0;
    vector<PI >::iterator it;
    while(true)
    {
        if(c==n)
          break;
        i=pp.top().ss;
        //cout<<i<<" ";
        if(vis[i]!=1)
        w=w+pp.top().ff;
        vis[i]=1;
        c++;
        pp.pop();
        for(x=1;x<=n;x++)
        {
            if(v[i][x]!=-1)
            {

            a=x;
            b=v[i][x];
            if(!vis[a] && b<k[a])
            {
                k[a]=b;
                p[a]=i;
                pp.push(mp(b,a));

            }
           }
       }
    }
}
int main()
{
    fast

    LL n,m,x,i,j,r,s;
    /*pp.push(mp(2,3));
    pp.push(mp(3,4));*/
    cin>>n>>m;
    LL k[n+1],p[n+1];
    v.resize(n+1);
    for(x=1;x<n+1;x++)
    {
        k[x]=INF;
        p[x]=-1;
    }
    for(x=0;x<m;x++)
    {
        cin>>i>>j>>r;
        /*v[i].pb(mp(j,r));
        v[j].pb(mp(i,r));*/
        if(v[i][j]!=-1)
        {
            if(v[i][j]>r)
            {
                v[i][j]=r;
                v[j][i]=r;
            }
       }
       else
       {
           v[i][j]=r;
           v[j][i]=r;
       }


    }
    cin>>s;
    prim(s,k,p,n);
    cout<<w;
    //cout<<pp.top().ss;    
}

I was not able to implement the function which searches a particular value i.e the vertex and changes it's key value instead I pushed the changed pair, using

pp.push(mp(b,a));

I was able to get some test cases right by using the if statement

if(c==n)
break;

where 'c' represents the count of vertexes visited.

Answer 1

标准 std::priority_queue 不允许在其中达到峰值，因此无法更改优先级键。这是一个经典的队列实现，在一侧推送元素并在另一侧弹出它们。因此，您可能应该寻找堆数据结构的更通用的实现。

如果您坚持使用 std::priority_queue，您可能需要做一些丑陋的事情，例如将完整的队列内容弹出到 vector 、更新元素和恢复队列。