这是涉及Dijkstra算法找到一个植根于一个给定的最短距离树一个简单的问题顶点。下面是一个被录取的code：

This is a simple problem involving Dijkstra's Algorithm to find shortest distance tree rooted at a given vertex. Following is the code that got accepted:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<deque>
#include<queue>
#include<utility>
#include<vector>
#include<climits>
#include<algorithm>
#include<stack>
using namespace std;
bool debug=false;
typedef long long int lld;
typedef unsigned long long int llu;
struct compare_vertex{
    bool operator()(const pair<int,lld> &p1 , const pair<int,lld> p2){
        return p1.second<p2.second;
    }
};
typedef priority_queue<pair<int,lld> , vector<pair<int,lld> > , compare_vertex> node_pq;
class Solver{
    int n , e , t , m;
    vector<deque<pair<int,lld> > > adjList;
    vector<lld> min_dist;
    node_pq pq;
    void push_node(int index , lld dist){
        if(min_dist[index] < dist){
            return;
        }
        pq.push(make_pair(index , dist));
        min_dist[index] = dist;
    }
public:
    Solver(){
        scanf("%d",&n);
        adjList = vector<deque<pair<int,lld> > >(n);
        min_dist= vector<lld>(n , INT_MAX);

        scanf("%d",&e);
        --e;
        scanf("%d",&t);
        scanf("%d",&m);

        int x , y ;
        lld z;
        for(int i=0;i<m;++i){
            scanf("%d %d %lld",&x , &y , &z);
            --x;--y;
            adjList[y].push_back(make_pair(x , z));
        }
    }
    int solve(){
        push_node(e , 0);

        int size;
        pair<int,lld> vertex;
        while(!pq.empty()){
            vertex = pq.top();
            pq.pop();

            size = adjList[vertex.first].size();
            for(int i=0;i<size;++i){
                push_node(adjList[vertex.first][i].first , vertex.second +   adjList[vertex.first][i].second);
            }
        }

        int count = 0;
        for(int i=0;i<n;++i){
            count += min_dist[i]<=t ? 1 : 0;
        }

        return count;
    }
};
int main(int argc , char **argv)
{
    if(argc>1 && strcmp(argv[1],"DEBUG")==0) debug=true;
    Solver s;
    printf("%d\n",s.solve());
    return 0;
}

的算法是贪婪的，所以我们逐步选择最接近顶点到树中。这意味着，一旦一个顶点被选中，将不会有从根任何较短的路径。因此，重新审视一个顶点，看看目前的距离小于$ P $短pvious距离是徒劳的（这是我们做的Bellman-Ford算法​​）。所以，在push_node函数返回条件应该是：

The algorithm is greedy, so we incrementally choose the closest vertex to the tree. This means, that once a vertex is chosen, there will not be any shorter path from the root. So, revisiting a vertex to see if the current distance is shorter than the previous distance is futile (this is something that we do in Bellman–Ford algorithm). So, the return condition in push_node function should have been:

if(min_dist[index] != INT_MAX){
    return; 
}

但是，这给了错误的答案。起初，我觉得有可能会在int数据类型溢出，所以我改变了所有的距离变量得到long long int（其中推了我一把，通过2个测试案例）。但还是上面给出错误的答案。我在哪里去了？

But this gives Wrong Answer. Initially I thought there might be an overflow on int datatype, so I changed all the distance variables to long long int (which pushed me through 2 more test cases). But still the above gives wrong answer. Where am I going wrong?

推荐答案

只要顶点不从优先级队列弹出，也就是说，只要它不是从根本上最接近的未完成的顶点，你还是可以找到更短路径到它。如果你这样做

As long as a vertex is not popped from the priority queue, i.e. as long as it is not the closest unfinished vertex from the root, you can still find shorter paths to it. If you do

if(min_dist[index] != INT_MAX){
    return; 
}

你永远只能找到一个路径，你会忽略那些后来发现更短的路径，给你错误的解决方案。

you can only ever find one path and you will ignore shorter paths that are found later, giving you wrong solutions.