Реализация алгоритма Дейкстры с использованием множества в C ++ - PullRequest
Новая
       10

Реализация алгоритма Дейкстры с использованием множества в C ++

0 голосов
/ 17 января 2019

Я пытался реализовать Дейкстру, используя заданную структуру данных в C ++. Я писал код на 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]<<" ";
}

1 Ответ

0 голосов
/ 18 января 2019

Проигнорируйте это, я понял это. (Кстати, код работает. И логично звучит, не стесняйтесь использовать его при необходимости.)

...