優先級隊列

Question

這是我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; 

()運營商在這方面有什麼用？我的意思是它在代碼中的功能如何？

另外爲什麼我們在operator()中使用&？

此外，該比較器如何在優先級隊列定義中工作？ 爲什麼我們在運算符定義中使用常量？

我的意思是說怎麼也正是這種比較在運營商的工作和着我們使用任何 其他符號作爲= * @或其他任何代替（）

Answer 1

在聲明變量（包括函數參數），該&將該變量標記爲參考。對某些類型的參數使用引用是非常基本和普遍的事情，部分原因是它傳遞參數而不創建副本（對於例如std::vector這麼好），並且還允許非函數中的非const引用作爲輸出參數。

至於在這樣的結構中使用operator()，它使得結構function objects的實例，換句話說，可以像函數一樣調用的對象。

Answer 2

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

通過重載()操作

這傳遞給priority_queue作爲比較類

&被用來傳遞pair恆定參考創建function object，使得沒有任何的實際複製（通過將它們作爲參考傳遞），同時該函數不能修改它們的值（通過使用const關鍵字）

通過使用此函數對象，隊列確定如何插入值（對）。

在這種情況下，對的第二個值用於比較。

Answer 3

我想你的問題是關於行priority_queue<pp,vector<pp>,pri> q;？

這聲明瞭類型爲priority_queue<pp,vector<pp>,pri>的變量q。 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來排序其元素。如果元素不能直接比較，或者默認值不合適，那麼您可以提供自己的元素。在這種情況下，元素將按每個元素pair中的second成員排序。

Answer 4

基本上相同，其他的答案，只是更詳細一點 - 運營商（）的代碼是什麼定義優先級隊列應該怎麼做比較，以確定在隊列中項目的優先級。使用這種類型的框架，可以定義一個優先級隊列來存儲任何類型的對象，並且優先級隊列可以根據您希望在對象上進行的任何類型的自定義排序來排序。

Answer 5

我認爲你寫的比較函數是錯誤的。

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可以看到表達排版（A，B），其中comp爲這種類型，a和b是元件的目的在容器中，如果a在該函數定義的嚴格弱順序中被認爲是在b之前返回，則返回true。

因爲在Dijkstra算法，具有較小值的節點應該有更高的優先級，因此，我們這裏使用的操作者應

p1.second>p2.second 

（通過使用代碼來解決一個問題，我花了很長時間有時候要弄清楚這個問題，我的程序的結果總是與正確的不同） （順便說一下，在Dijkstra算法本身中，我認爲一旦節點被彈出爲最小的節點，就沒有必要彈出它一次更新所有連接到它的節點。這可以節省大量的時間。）

Answer 6

我refactore d代碼並用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; 
}