I was trying to solve the problem MICEMAZE from spoj. Here is the link to the problem MICEMAZE. I reversed all the edges and then performed dijkstra using source vertex as the “exit cell”. But my code is giving TLE. Can someone help.
#include<bits/stdc++.h>
#define mp make_pair
#define ll long long int
using namespace std;
ll dijkstra(vector<pair<ll , ll> > adj[] ,ll n , ll e , ll t){
priority_queue<pair<ll , ll> , vector<pair<ll,ll> > , greater<pair<ll , ll> > > pq;
vector<ll> distance(n+1 , LLONG_MAX);
vector<bool> isVisited(n+1 , false);
distance[e] = 0;
pq.push(mp(0 , e));
for(ll i=0;i<n;++i){
pair<ll,ll> p = pq.top();
ll x = p.second , w = p.first;
pq.pop();
if(isVisited[x]) {--i;continue;}
isVisited[x] = true;
for(ll j=0;j<adj[x].size();++j){
ll y = adj[x][j].first , d = adj[x][j].second;
if(w+d < distance[y]){
distance[y] = w+d;
pq.push(mp(distance[y] , y));
}
}
}
ll ans = 0;
for(ll i=1;i<=n;++i) if(distance[i] <= t) ++ans;
return ans;
}
int main(){
ll n , e , t , q;
scanf("%lli%lli%lli%lli",&n,&e,&t,&q);
vector<pair<ll , ll> > adj[n+1];
while(q--){
ll a , b , c;
scanf("%lli%lli%lli",&a,&b,&c);
adj[b].push_back(mp(a , c));
}
cout << dijkstra(adj , n , e, t) << endl;
return 0;
}
Here is a link to my code My Code
Thanks in advance