Dijkstra

Zdravo. Probuvam da iskucam dijkstra samo so priority_queue, bez koristenje niza dist[]. Kodot ne mi pecati nisto. Kje moze da mi se objasni kade mi e greskata?

#include <bits/stdc++.h>

using namespace std;

const int MAX= 1e5+10;
const int INF=(1<<30);
int N,M;
int START,END;
bool vis[MAX];
vector<pair<int,int> > graph[MAX];
struct node{
    int idx;
    int cost;
    node(){}
    node(int _idx, int _cost)
    {
        idx=_idx;
        cost=_cost;
    }

bool operator < (const node &TMP) const{
        return cost > TMP.cost;

}

};

void dijkstra()
{
    memset(vis,false,sizeof(vis));
    priority_queue<node> q;
    q.push(node(START,0));
    while(!q.empty())
    {
        node curr=q.top();
        q.pop();
        if(vis[curr.idx]==false)
        {
            continue;
        }
        if(curr.idx==END)
        {
            cout<<curr.cost<<endl;
        }
        vis[curr.idx]=true;
        for(int i=0; i<(int)graph[i].size(); i++)
        {
            int sosed=graph[curr.idx][i].first;
            int val=graph[curr.idx][i].second;
            if(!vis[sosed]&& curr.cost > curr.cost + val)
            {
                q.push(node(sosed,curr.cost + val));
            }

}
    }

}

int main()
{
    cin>>N>>M;
    for(int i=0; i<M; i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        a--;
        b--;
        graph[a].push_back(make_pair(b,c));
        graph[b].push_back(make_pair(a,c));
    }
    cin>>START>>END;
    START--;
    END--;
    dijkstra();
    return 0;
}

BATIR wrote:Zdravo. Probuvam da iskucam dijkstra samo so priority_queue, bez koristenje niza dist[]. Kodot ne mi pecati nisto. Kje moze da mi se objasni kade mi e greskata?

Ако нешто не работи како што треба, можеш да пробаш со debug-ирање (види во IDE-то кое го користиш), а можеш и да пробаш да додадеш неколку наредби за печатење за да си ја најдеш грешката. Ќе ти користи и за време на натпревар.

Треба да смениш повеќе работи иначе, еве некои

Тука веројатно мислиш true наместо false.

Тука не мислиш graph[i].size() него веројатно graph[curr.idx].size()

Тука тргни го вториот услов (по &&)

A kako bi bilo ako namesto priority_queue koristam obicen queue?

BATIR wrote:A kako bi bilo ako namesto priority_queue koristam obicen queue?

Што сакаш да постигнеш со тоа, за да може да ти одговориме? Не работи така алгоритамот Dijkstra, и (на тој начин) не можеш да ја постигнеш истата сложеност.

Epa nemam konkreten odgovor, samo sakav da znam kako bi bil kodot so obicno queue.