DOUBT IN CSES PROBLEMSET — Graphs ( Shortest Path — I )

Revision en1, by shreyas_171, 2021-07-08 09:55:56

Hey everyone! I hope you are doing extremely well. I have been doing Graphs from CSES Problem set and unfortunately got stuck in SHORTEST PATH — 1 Problem.

I'm getting WA in 6th , 7th , 8th , 9th and 12th TestCase. Though I have used long long int then also , its giving WA .

If you have got AC, then please help me out.

Thank you, to give your precious time to read this blog and pointing out mistakes :)

Keep Coding !!

#include <bits/stdc++.h>
using namespace std;

#define fast                    ios_base::sync_with_stdio(false);  cin.tie(NULL);
#define time                    cerr<<"Time taken : " <<(float)clock()/CLOCKS_PER_SEC <<" secs"<<"\n"  ;
#define F                       first
#define S                       second
#define pb                      push_back
typedef long long int           ll  ;
#define INF                     1e15
#define MOD                     1000000007

#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1 << " | "; __f(comma + 1, args...);
}
#else
#define trace(...)
#endif


int32_t main() {

  fast ;

  ll n , m ;

  cin >> n >> m ;

  vector<vector<pair<ll, ll>>>adj;

  adj.resize(n + 1)  ;

  for (ll i = 0; i < m ; i++) {
    ll a , b , w ;
    cin >> a >> b >> w;
    adj[a].pb({b, w}) ;
  }



  vector<ll>dist ;

  dist.resize(n + 1)  ;

  for (ll i = 0 ; i <= n ; i++) {
    dist[i] = INT_MAX;
  }

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

  dist[1] = 0  ;

  pq.push({0, 1})  ;

  while (!pq.empty()) {

    ll d = pq.top().F ;
    ll n = pq.top().S;
    pq.pop()  ;

    if (dist[n] < d ) continue  ;

    for (auto x : adj[n]) {

      ll n1 = x.F;
      ll d1 = x.S;

      if (dist[n1] <= d1 + d) continue  ;
      else if (dist[n1] >  d + d1 ) {
        dist[n1] = d + d1;
        pq.push({dist[n1] , n1}) ;
      }
    }
  }

  for (ll i = 1; i <= n; i++) {
    cout << dist[i] << " "  ;
  }


  return 0  ;
}

Tags #cf, #cp, #codefoces, #graph theory

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English shreyas_171 2021-07-08 09:55:56 2446 Initial revision (published)