在 C++ 中使用集合实现 Dijkstra 算法

Question

我试图在 C++ 中使用集合数据结构来实现 Dijkstra。我在 C++14 中编码，代码中似乎有些乱序，因为它在 Codechef IDE 中没有给我正确的答案，在 DevCpp 上它甚至没有编译！

我认为代码逻辑合理，只有语义错误。

#define INF 1000000000
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
int main()
{
    int n,e;
    cin>>n>>e;
    vector<vector<pair<int,int> > > adj(n);
    vector<pair<int,int> > :: iterator v;
    for(int i=0;i<e;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        adj[x].push_back({y,z});
    }
    vector<int> d(n,INF);
    vector<int> p(n,-1);
    set<pair<int,int> > q;
    for(int i=0;i<n;i++)
    {
        q.insert({INF,i});
    }
    int s;
    cin>>s;
    q.erase({INF,s});
    q.insert({0,s});
    d[s]=0;
    while(!q.empty())
    {
        int u=(*q.begin()).second;
        q.erase(q.begin());
        for(v=adj[u].begin();v!=adj[u].end();v++)
        {
            int to=(*v).first;
            int len=(*v).second;
            if(d[to]>d[u]+len)
            {
                q.erase({d[to],to});
                d[to]=d[u]+len;
                p[to]=u;
                q.insert({d[to],to});
            }
        }
    }
    cout<<endl;
    for(int i=0;i<n;i++)
    cout<<d[i]<<" ";
}

Answer 1

忽略这个我已经弄明白了。（顺便说一句，代码有效。逻辑上合理，如果需要可以随意使用它。）

在 C++ 中使用集合实现 Dijkstra 算法

Implementation of Dijkstra's Algorithm using set in C++

implementation

dijkstra