Please read the new rule regarding the restriction on the use of AI tools. ×

utkarshchauhan2812's blog

By utkarshchauhan2812, history, 9 months ago, In English

i am having trouble finding out the reason for tle in my code(for the last case of the problem shortest routes 1 of cses:https://cses.fi/problemset/task/1671/) below is my code for the same

Your code here...
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pi = pair<int, int>;
#define f first
#define s second
#define mp make_pair
void setIO(string name = "") {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	if (sz(name)) {
		freopen((name + ".in").c_str(), "r", stdin);
		freopen((name + ".out").c_str(), "w", stdout);
	}
}


int main() {
	ll n, m;
	cin >> n >> m;

	vector<pair<ll, ll>>adj[n + 1];
	for (int i = 0; i < m; i++) {
		ll a, b, c;
		cin >> a >> b >> c;

		adj[a].push_back({b, c});
		// adj[b].push_back({a, c});
	}
	vector<ll>distance(n + 1, LLONG_MAX);
	distance[1] = 0;
	priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>>q;
	q.push({0, 1});
	while (!q.empty()) {
		ll d = q.top().first;
		int node = q.top().second;	
		q.pop();
		for (auto i : adj[node]) {
			int it = i.first;
			int wt = i.second;
			if (d + wt < distance[it]) {
				distance[it] = d + wt;
				q.push({distance[it], it});
			}
		}
	}
	for (int i = 1; i <= n; i++)cout << distance[i] << " ";
	return 0;
}

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by utkarshchauhan2812 (previous revision, new revision, compare).

»
9 months ago, # |
  Vote: I like it +17 Vote: I do not like it

Hi, You are not checking for dead nodes when you are picking the nodes that are at the least possible distance from the root in the priority queue. Here's the correct segment of the code :

	while (!q.empty()) {
		ll d = q.top().first;
		int node = q.top().second;	
		q.pop();
                if(distance[node] < d) continue ;
		for (auto i : adj[node]) {
			int it = i.first;
			int wt = i.second;
			if (d + wt < distance[it]) {
				distance[it] = d + wt;
				q.push({distance[it], it});
			}
		}
	}
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    oh that was so silly of me . thank's a lot!

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      Now try to come up with a test case where your version fails. It’s a good exercise.

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        for the incorrect code lets say at some point we have a node A with distance 5 in the q while we also have a node A with distance 10 in the q . since we will explore node A with dist 5 first(min heap) as a result the dist of all the neighbour nodes will be figured out and updated. now we come to A-10 this will not change the distance of any node but will iterate through the neighbours(let's say n') only when n' is a number of large order will this approach fail so how exactly should i come up with this huge test case.

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Good point! So you’d somehow need to have A added multiple times in the queue and also have many outgoing edges from A. How could you achieve that?

          • »
            »
            »
            »
            »
            »
            9 months ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            are you implying a self loop? cause in that way A will keep on being pushed into the heap while also let us say it has 1e5 neighbours so it will have to iterate 1e5 times more , if we have multiple self loops like these in lot of nodes(B,C...) which in turn have tons(of the order of 1e4-5) of neighbours i can see how it adds up to the time complexity . Am i missing something(Sorry i am not that smart)?

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

add this condition below the q.pop()

if (d > distance[node])
{
  continue;
}