Shortest Routes I (CSES Problem Set)

Ritwik Chakraborty

·

Follow

Jul 9, 2021

--

Listen

Share

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] << " ";}