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;
}
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?
add this condition below the q.pop()
if (d > distance[node]) { continue; }