Problem Link

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long int
#define ld double
#define REP(i, x, n) for (ll i = x; i < n; i++)
#define SZ(v) (ll) v.size()
#define endl "\n"
#define ff first
#define ss second
#define PQ_MIN priority_queue<ll, vector<ll>, greater<ll>>
#define PQ priority_queue<int>
#define pbds tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define setbit(x) __builtin_popcount(x)
#define prec(n) fixed <<…

problem Link

ll n, m;vector<pair<ll, ll>> v[nxm];void solve(){cin >> n >> m;REP(i, 0, m){ll z, x, y;cin >> x >> y >> z;v[x].pb(mp(y, z));}// priority_queue<ii, vector<ii>, greater<ii>> pq;set<ii> pq;ll src = 1;pq.insert({0, src});ll dis[n + 1];REP(i, 1, n + 1)dis[i] = INF;dis[1] = 0;while (!pq.empty()){ii curr = *pq.begin();pq.erase(pq.begin());for (auto j : v[curr.ss]){if (dis[j.ff] > j.ss + curr.ff){// high chance we have put {dis[j.ff],j.ff} previously in queue let's remove themauto it = pq.find(mp(dis[j.ff], j.ff));if (it != pq.end())pq.erase(it);dis[j.ff] = j.ss + curr.ff;pq.insert(mp(dis[j.ff], j.ff));}}}REP(i, 1, n + 1)cout << dis[i] << " ";}

Ritwik Chakraborty

software developer

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store