3

これはダイクストラのアルゴリズムの私のコードです:

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>

#define pp pair<int,int>
using namespace std;
struct pri
{
    int operator() (const pair<int,int>&p1,const pair<int,int>&p2)
    {
        return p1.second<p2.second;
    }
}p;
int main()
{
    priority_queue<pp,vector<pp>,pri> q;
    int n;
    cin>>n;
    vector<pp> g[n+1];
    int e,u,v,w,i;
    cin>>e;
    for(i=0;i<e;i++)
    {
        cin>>u>>v>>w;
        g[u].push_back(pp(v,w));
        g[v].push_back(pp(u,w));
    }
    int s;
    cin>>s;
    int d[n+1];
    for(i=1;i<=n;i++)
        d[i]=999;
    d[s]=0;
    q.push(pp(s,d[s]));
    while(!q.empty())
    {
        u=q.top().first;
        q.pop();
        int size=g[u].size();
        for(int i=0;i<size;i++)
        {
            v=g[u][i].first;
            w=g[u][i].second;
            cout<<u<<" "<<" "<<w<<endl;
            if(d[v]>d[u]+w)
            {
                d[v]=d[u]+w;
                q.push(pp(v,d[v]));
            }
        }
    }
    for(i=1;i<=n;i++)
        printf("node %d,min weight=%d\n",i,d[i]);
    return 0;
}

これで私はの働きを理解できません

 priority_queue<pp,vector<pp>,pri> q;

それは次のことに関連しています。

struct pri
{
    int operator() (const pair<int,int>&p1,const pair<int,int>&p2)
    {
        return p1.second<p2.second;
    }
}p;

()これで演算子は何に使用されますか? このコードでどのように機能するのですか？

&また、なぜinを使用するのoperator()ですか?

また、このコンパレータはプライオリティ キュー定義でどのように機能しますか? また、演算子の定義で定数を使用するのはなぜですか?

演算子でこの比較が正確にどのように機能しているかを言いたいのですが、他の記号を = * @ または () の代わりに使用することはできません

4

6 に答える 6

0

このコードをリファクタリングし、hackerrank で確認しました。

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <iterator>
#include <algorithm>
#include <functional>

using namespace std;

struct pri
{
    typedef pair<int,int> pp;
    typedef deque<pri::pp > list;
    typedef vector< pri::list > graph;
    int operator() (pp&p1,const pp&p2)
    {
        return p1.second>p2.second;
    }
    typedef priority_queue< pri::pp, pri::list, pri > queue;
};

static int f1(const int x){ return x==std::numeric_limits<int>().max()?-1:x; }

int main()
{
    int t;
    cin>>t;
    while(t--){
        int n,e;
        cin>>n>>e;
        pri::graph g(n+1);
        for(int i(0);i<e;i++){
            int u,v,w;
            cin>>u>>v>>w;
            g[u].push_back(pri::pp(v,w));
            g[v].push_back(pri::pp(u,w));
        }
        vector<int> d(n+1,std::numeric_limits<int>().max());
        int s;        cin>>s;
        d[s]=0;
        pri::queue q;
        q.push(pri::pp(s,d[s]));
        set<int> vs;
        while(!q.empty()) {
            const int u(q.top().first);
            const pri::list& gu(g[u]);
            q.pop();
            vs.insert(u);
            for( pri::list::const_iterator i(gu.begin()); i != gu.end(); ++i ) {
                const int v(i->first),  w(i->second);
                if( vs.find(v)==vs.end() ){
//                  cout<<u<<" "<<v<<" "<<w<<endl;
                    if( d[v]>d[u]+w ) {
                        d[v]=d[u]+w;
                        q.push(pri::pp(v,d[v]));
                    }
                }
            }
        }
        copy_if(d.begin()+1,d.end(),d.begin(),std::bind2nd(std::not_equal_to<int>(),0));
        transform(d.begin(),d.end()-2,ostream_iterator<int>(cout," "),f1);
        cout<<endl;
    }
    return 0;
}
于 2015-10-31T01:18:27.493 に答える
0

基本的に他の回答と同じですが、もう少し詳しく説明します.operator()コードは、キュー内のアイテムの優先度を決定するために優先度キューが比較を行う方法を定義するものです。このタイプのフレームワークを使用すると、任意のタイプのオブジェクトを格納するように定義されたプライオリティ キューを持つことができ、プライオリティ キューは、オブジェクトに必要な任意の種類のカスタム順序に従って並べ替えることができます。

于 2013-07-27T14:14:06.847 に答える