Can Someone Please Explain why this code is giving MLE at test case 45. 251218571
My Code
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf = 1e18 + 10;
ll max(ll x, ll y) { return x > y ? x : y; }
ll min(ll x, ll y) { return x < y ? x : y; }
#define f(i, m, n) for (ll i = (ll)m; i < (ll)n; i++)
#define f_(i, n, m) for (ll i = (ll)n; i >= (ll)m; i--)
#define fa(i, x) for (auto i : x)
#define vll vector<ll>
#define vvll vector<vll>
#define vvvll vector<vvll>
#define pll pair<ll, ll>
#define vpll vector<pll>
#define vvpll vector<vpll>
#define ff first
#define ss second
#define pb push_back
#define nl cout << "\n";
deque<tuple<ll, ll, ll>> dq;
ll n, m;
ll s, e;
map<pll, ll> dist;
void solve()
{
//CODE HERE
dist.clear();
cin >> n >> m;
vvpll adj(n + 1);
f(i, 0, m)
{
ll u, v, c;
cin >> u >> v >> c;
adj[u].pb({v, c});
adj[v].pb({u, c});
}
cin >> s >> e;
dq.push_back({0, s, 0});
while (!dq.empty())
{
auto [dd, node, clr] = dq.front();
dq.pop_front();
if (node == e)
{
cout << dd << " ";
break;
}
dist[{node, clr}] = dd;
fa(&nbr, adj[node])
{
if (!dist.count({nbr.ff, nbr.ss}))
{
if (clr != nbr.ss)
dq.push_back({dd + 1, nbr.ff, nbr.ss});
else
dq.push_front({dd, nbr.ff, nbr.ss});
}
}
}
dq.clear();
nl
}
signed main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
ll no_of_testcases = 1;
cin >> no_of_testcases;
f(curr_testcase, 1, no_of_testcases + 1)
{
solve();
}
}
Thanks.
Your solution is doing BFS in brute force way, ignoring the constraints, and pushing so many nodes into the deque and dist map. If I'm not wrong, you'll push all possible pairs of {station, subway lines} that are connected. No wonder it's MLE and eventually TLE.
You need to change your approach. I left a hint in a comment if you need it. (It's based on editorial)