I solved this problem using Dijkstra with a normal queue instead of a priority queue because interestingly I was getting a TLE when I used the priority queue. My understanding is that Dijkstra with priority queue should perform better. I tried analyzing as to why is this the case? I came up with a thought that it is so because the question uses test cases with graphs having edges from 1 to n in increasing order of their weights so it is a waste of time to maintain a priority queue and hence the TLE. I would like to know if this is exactly the case an I'm not missing anything. Here is my solution to the problem:
#include <bits/stdc++.h>
using namespace std;
#define INF 100000000
queue<pair<long, int>> pi;
vector<long> dist;
map<int, vector<pair<int, long>>> mp;
int main() {
int m = 0, n = 0;
cin >> m >> n;
while (n--) {
int l = 0, k = 0, j = 0;
cin >> l >> k >> j;
mp[l].push_back(make_pair(k, j));
mp[k].push_back(make_pair(l, j)); // for undirected edge
}
dist.assign(m + 1, INF);
dist[1] = 0;
pi.push(make_pair(0, 1));
while (!pi.empty()) {
pair<int, int> p = pi.front(); pi.pop();
int u = p.second; long w = p.first;
if (w > dist[u]) continue;
for (auto e : mp[u]) {
if (max(dist[u], e.second) < dist[e.first]) {
dist[e.first] = max(dist[u], e.second);
if (e.first != m)
pi.push(make_pair(dist[e.first], e.first));
}
}
}
if (dist[m] == INF) cout << "NO PATH EXISTS" << endl;
else cout << dist[m] << endl;
return 0;
}
Did you change a default comparator of priority queue? If not, then, of course, it would be slower