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;
}
Auto comment: topic has been updated by utkarshchauhan2812 (previous revision, new revision, compare).
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 :
oh that was so silly of me . thank's a lot!
Now try to come up with a test case where your version fails. It’s a good exercise.
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.
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?
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)?
add this condition below the q.pop()
if (d > distance[node]) { continue; }