c++ - dijkstra 实现给出了错误的输出

Question

我正在尝试解决我对 dijkstra 算法的理解的问题。这就是提到的问题:https://www.hackerrank.com/challenges/dijkstrashortreach .只有第一个测试用例被接受，所有其他测试用例都是错误的。请任何人提示我我的实现可能有什么问题。据我了解的算法，我已经正确地实现了它

这是我的代码:

#include<bits/stdc++.h>
using namespace std;
#define MAX 100001
#define INF INT_MAX
#define pii pair< int, int >
#define pb(x) push_back(x)

int main() {
int i, u, v, w, sz, nodes, edges, starting;
int t;
cin>>t;
while(t--){
    priority_queue< pii, vector< pii >, greater< pii >  > Q;
    vector< pii > G[MAX];
    int D[MAX];
    bool F[MAX];
    // create graph
    scanf("%d %d", &nodes, &edges);
    for(i=0; i<edges; i++) {
        scanf("%d %d %d", &u, &v, &w);
        G[u].pb(pii(v, w));
        G[v].pb(pii(u, w)); // for undirected
    }
    scanf("%d", &starting);
    // initialize distance vector
    for(i=1; i<=nodes; i++) { D[i] = INF; F[u] = 0;}
    D[starting] = 0;
    Q.push(pii(starting, 0));
    // dijkstra
    while(!Q.empty()) {
        u = Q.top().first;
        Q.pop();
        if(F[u]) continue;
        sz = G[u].size();
        for(i=0; i<sz; i++) {
            v = G[u][i].first;
            w = G[u][i].second;
            if(!F[v] && D[u]+w < D[v]) {
                    D[v] = D[u] + w;
                    Q.push(pii(v, D[v]));
            }
        }
        F[u] = 1; // done with u
    }
// result
    for(i=1; i<=nodes; i++){
        if(i!=starting){
        if(D[i]==INF)printf("%d ",-1);
        printf("%d ",D[i]);
    }
  }
}
return 0;
}

Answer 1

您的最小堆不正确，您需要为您的对定义比较函数。使用 greater是不足够的。

这是 C++ 用于 pair 的比较,

template <class T1, class T2>
  bool operator<  (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs)
{ return lhs.first<rhs.first || (!(rhs.first<lhs.first) && lhs.second<rhs.second); }

你可以看到，它总是比较first然后 second ，但你的理想行为应该比较second之前 first (对于您的情况，首先是节点 ID，其次是它的权重)。更多详情请看here

或者，您可以反转 first 的位置和 second在你的对中。

还有一个问题是

for(i=1; i<=nodes; i++) { D[i] = INF; F[u] = 0;}

应该是:

for(i=1; i<=nodes; i++) { D[i] = INF; F[i] = 0;}

最后一个问题是，对于每个新的测试用例，您需要在新行 中打印结果，另外，您的最后一个 if 条件不正确。应该是:

for(i=1; i<=nodes; i++){
    if(i!=starting){
        if(D[i]==INF)
            cout << -1 << " ";
        else    
            cout << D[i] << " ";
    }
}
cout << endl;  

我的 code在所有这些更改之后已被接受。