I was solving this question: http://www.codechef.com/problems/DIGJUMP
I used Dijkstra but it is showing TLE. I have been trying to solve this, but was unable to. Can anyone help me finding an issue in this code? Help will be highly appreciated😃
You can see the code on this ideone link too.
TIZ8TF - Online C++ Compiler & Debugging Tool - Ideone.com
#include <bits/stdc++.h>
using namespace std;typedef long long ll;
#define FAST_FURIER ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pb push_back
#define ppb pop_back
#define mk make_pair
#define sorta(v) sort(v.begin(), v.end())
#define sortd(v) sort(v.begin(), v.end(), comp)
#define rep(i,a,N) for(ll i=a;i<N;i++)
#define rrep(i,a,N) for(ll i=a;i>N;i--)
#define print(v) for(ll ite=0;ite<v.size();ite++){cout<<v[ite]<<' ';}cout<<endl;
#define M 1000000007
bool comp(ll x,ll y)
{
return x > y;
}
/*..............................code starts here........................*/
// C is first won in M
vector<int> adj[10];
vector<int> visited(100005,0);
vector<int> dist(100005,1e8);
int n;
string s;
int dijkstra() {
set<pair<int,int> > q;
q.insert(mk(0,0));
dist[0] = 0;
while(!q.empty()) {
int index = (*q.begin()).second; q.erase(q.begin());
visited[index] = 1;
for(int node: adj[s[index]-'0']){
if(!visited[node])
if(dist[index]+1 < dist[node]) {
dist[node] = dist[index] + 1;
q.insert(mk(dist[node], node));
}
if(node-1 >= 0 and !visited[node-1] and dist[node]+1 < dist[node-1]){
dist[node-1] = dist[node]+1;
q.insert(mk(dist[node-1], node -1));
}
if(node+1 < n and !visited[node+1] and dist[node]+1 < dist[node+1]){
dist[node+1] = dist[node]+1;
q.insert(mk(dist[node+1], node+1));
}
}
}
return dist[n-1];
}
void solve(){
cin >> s;
n = s.length();
rep(i,0,n){
adj[s[i]-'0'].pb(i);
}
cout << dijkstra() << endl;
}
int main() {
FAST_FURIER;
int tt=1;
// cin >> tt;
while(tt--){
solve();
}
}