3

这是我的 Dijkstra 算法代码：

#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

3

我认为您编写的比较功能是错误的。

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

正确的应该是哪个

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

因为在priority_queque中你可以发现表达式comp(a,b)，其中comp 是这种类型的对象，a 和b 是容器中的元素，如果a 被认为在严格的弱排序中排在b 之前，则应该返回true函数定义。

因为在 Dijkstra 算法中，值较小的节点应该具有较高的优先级，因此我们这里使用的算子应该是

p1.second>p2.second

（通过使用你的代码解决一个问题，我花了很长时间才弄清楚这个问题，我的程序的结果总是与正确的结果不同。）（顺便说一下，在 Dijkstra 算法本身中，我认为一旦一个节点是弹出的最小的，不需要再弹出并更新所有连接的节点，这样可以节省很多时间。）

于 2014-05-31T23:42:51.473 回答
2 
struct pri {
    int operator() (const pair<int,int>&p1,const pair<int,int>&p2)
    {
        return p1.second<p2.second;
    }
}p;

通过重载运算符创建函数对象()

这作为比较类传递给priority_queue

&用于将对作为常量引用传递，确保不会复制实际参数（通过将它们作为引用传递），同时函数不能修改它们的值（通过使用const关键字）

使用此函数对象，队列确定如何插入值（对）。

在这种情况下，pair 的第二个值用于比较。

于 2013-07-27T13:38:03.747 回答
1

在声明变量（包括函数参数）时，&就是将变量标记为引用。对某些类型的参数使用引用是非常基本和常见的事情，部分原因是它在不创建副本的情况下传递参数（例如 a 非常好std::vector），并且它还允许在函数中更改非常量引用作为输出形式争论。

至于operator()在这样的结构中的使用，它使结构函数对象的实例，换句话说，可以像函数一样被调用的对象。

于 2013-07-27T13:37:09.853 回答
1

我想你的问题是关于这条线的priority_queue<pp,vector<pp>,pri> q;？

这声明了一个q类型为 的变量priority_queue<pp,vector<pp>,pri>。priority_queue定义为

template<class T,
         class Container = vector<T>,
         class Compare = less<typename Container::value_type> >
class priority_queue;

所以，pp是元素的类型，vector<pp>是容器（与默认相同），pri是用于比较队列中项目的函数对象（Compare）。priority_queue用于Compare对其元素进行排序。如果元素不能直接比较，或者默认值不合适，那么您可以提供自己的。在这种情况下，元素将按second每个元素中的成员排序pair。

于 2013-07-27T13:38:28.903 回答
0

基本上与其他答案相同，只是更详细一点 - operator() 代码定义了优先级队列应如何进行比较以确定队列中的项目优先级。使用这种类型的框架，您可以定义一个优先级队列来存储任何类型的对象，并且可以根据您想要的对象上的任何类型的自定义排序来对优先级队列进行排序。

于 2013-07-27T14:14:06.847 回答
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 回答