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 ;
}
You're initializing
dist[i] = INT_MAX
but it should beLONG_LONG_MAX
. Always be careful about limits.Also, this is CSES, you can check that the output you're getting for those test cases is
INT_MAX
and realize where it came from.