I Need one help

help
#1

Today i was solving cses graph problems Shortest Routes I LINK and i am using Dijkstra’s algorithms and after submitting i am getting wrong answer , please help me to find out the error.
My Code

Code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define INF 0x3f3f3f3f
#define fastIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define all(x) x.begin(), x.end()
ll n, k, m, V, E;
vector<pair<ll,ll>> adj[1000005];
int main(){

cin >> V >> E;

for(ll i = 0; i<E; i++){

    ll a, b, c;

    cin >> a >> b >> c;

    --a;

    --b;

    adj[a].push_back({b , c});

}

priority_queue<pair<ll, ll>, vector<pair<ll, ll>> , greater<pair<ll, ll>> > pq;

vector<ll> dist(V, INF);

pq.push({0, 0}); // distance, source.

dist[0] = 0;

while(!pq.empty()){

    ll u = pq.top().second;

    pq.pop();

    for(auto p : adj[u]){

        ll v = p.first;

        ll w = p.second;

        if(dist[v] > w + dist[u]){

            dist[v] =  w + dist[u];

            pq.push({dist[v], v});

        }

    }

}



for(ll i = 0; i<V; i++){

    cout << dist[i] << " ";

}

return 0;

}

Thankyou in advance

#2 
/*
 
1) Initialize distances of all vertices as infinite.
 
2) Create an empty priority_queue pq.  Every item
   of pq is a pair (weight, vertex). Weight (or 
   distance) is used used as first item  of pair
   as first item is by default used to compare
   two pairs
 
3) Insert source vertex into pq and make its
   distance as 0.
 
4) While either pq doesn't become empty
    a) Extract minimum distance vertex from pq. 
       Let the extracted vertex be u.
    b) Loop through all adjacent of u and do 
       following for every vertex v.
 
           // If there is a shorter path to v
           // through u. 
           If dist[v] > dist[u] + weight(u, v)
 
               (i) Update distance of v, i.e., do
                     dist[v] = dist[u] + weight(u, v)
               (ii) Insert v into the pq (Even if v is
                    already there)
               
5) Print distance array dist[] to print all shortest
   paths. 
   
 
*/
 
 
 
// create adjacency list of pair 
// adj[u].pb({v,cost}) from u to v cost is cost
 
 
 
 
void Dijikistra(vector<pii>adj[] , lli v , lli source){
    
    lli dist[v+1];
    
    for(lli i=1;i<=v;i++)
        dist[i] = INF;
        
    dist[source] = 0;
    
    // min priority queue of pair 
    // where pair is < (cost from u to v)  , node >
    priority_queue<pii , vector<pii> , greater<pii> > pq;
    
    pq.push(make_pair(0,source));    // from source to source cost is 0
    
    
    while(!pq.empty()){
        
        pii mpair = pq.top();
        
        lli u  = mpair.S;
        
        pq.pop();
        
        if(dist[u]<mpair.F)
            continue;
        
        
        for(auto xt : adj[u]){
            
            lli v = xt.F;
            
            lli weight = xt.S;
            
            if(dist[v] > (dist[u] + weight) )
            {
               dist[v] = dist[u] + weight;
 
               pq.push(make_pair(dist[v] , v));
            }
            
        }
        
    }
 
 
    for(lli i=1;i<=v;i++)
        cout<<dist[i]<<" ";
    
}
 
 
 
 
int main(){
fastio
lli t=1;
//cin>>t;
chandan2();
while(t--) {
    lli v,e;
    cin>>v>>e;
    
    vector<pii>adj[v+1];
    
    loop(i,e){
        lli x,y,cost;
        cin>>x>>y>>cost;
        adj[x].pb(make_pair(y,cost));
    }
 
 
    Dijikistra(adj,v,1);
    
  }
return 0;
}
1 Like
#3

ThankYou bhaiya for your help.
But can could you see my code and tell me where i am lacking and writing the wrong code

#4

wait.

#5

okk

#6

U can see the test case on which it gave WA.

#7

YES