Hey , please help me in below given problem , a problem which is from Aug 14 long , I solved it by using Dijkistra’s algo , and it gets AC too , but same problem present on E-olymp contest with higher constraints in one test case it gives TLE .
Link_To_CC_Problem
Same_E-olymp_Problem [higher constraints]
My_Solution
You don’t need dijkstra, look up what 0-1 BFS is (and it’s probably hard to speed up dijkstra further anyway)
Ok, thanks for replying, I will learn 0-1 BFS and will apply in this question. 
bro i think even normal dijkstra’s algo work fine with that question also.
// Author : Amit Kumar
#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;
#define int int64_t
vector<vector<pair<int,int>>>graph;
vector<int>dist;
void dij(int start , int End){
priority_queue<pair<int,int> , vector<pair<int,int>> , greater<pair<int,int>>>pq;
pq.push(make_pair(0 , start));
dist[start] =0;
while(!pq.empty()){
int cost = pq.top().first;
int node = pq.top().second; pq.pop();
for(auto&itr:graph[node]){
if(dist[itr.first] > itr.second + dist[node]){
dist[itr.first] = itr.second + dist[node];
pq.push(make_pair(dist[itr.first] , itr.first));
}
}
}
}
signed main(void){
#ifdef HELL_JUDGE
freopen("input","r",stdin);
freopen("output","w",stdout);
freopen("error","w",stderr);
#endif
ios::sync_with_stdio(false); // FLUSH THE STREAM IF USING puts / printf / scanf/
cin.tie(nullptr); // DISABLE FOR INTERACTIVE PROBLEMS
cout.tie(nullptr); //
#ifdef HELL_JUDGE
auto INITIAL_TIME = high_resolution_clock::now();
#endif
int n , m; cin >> n >> m;
dist.assign(n+1 , INT_MAX);
graph.resize(n+1);
for(int i=0;i<n;++i){
int x,y; cin >> x >> y;
graph.at(x).emplace_back(make_pair(y,0));
graph.at(y).emplace_back(make_pair(x,1));
}
dij(1 , n);
if(dist[n] == INT_MAX){
cout << -1 << '\n';
}else{
cout << dist[n] << '\n';
}
#ifdef HELL_JUDGE
auto FINAL_TIME = high_resolution_clock::now();
cout << "Time : "
<< duration_cast<milliseconds>(FINAL_TIME-INITIAL_TIME).count()
<< " ms" << '\n';
#endif
return 0;
}
this is my implementation, (though it gives wrong answer on test case 1 and 4 ) but it take very less time. you code took 1235 ms on last test case but mine executed in 665 ms.
You only read in n edges
really sorry, but i didn’t get what you want to say. 
u scan n edges , scan m edges and try to submit your code give TLE
#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;
#define int int64_t
vector<vector<pair<int,int>>>graph;
vector<int>dist;
void dij(int start , int End){
priority_queue<pair<int,int> , vector<pair<int,int>> , greater<pair<int,int>>>pq;
pq.push(make_pair(0 , start));
dist[start] =0;
while(!pq.empty()){
int cost = pq.top().first;
int node = pq.top().second; pq.pop();
for(auto&itr:graph[node]){
if(dist[itr.first] > itr.second + dist[node]){
dist[itr.first] = itr.second + dist[node];
pq.push(make_pair(dist[itr.first] , itr.first));
}
}
}
}
signed main(void){
#ifdef HELL_JUDGE
freopen("input","r",stdin);
freopen("output","w",stdout);
freopen("error","w",stderr);
#endif
ios::sync_with_stdio(false); // FLUSH THE STREAM IF USING puts / printf / scanf/
cin.tie(nullptr); // DISABLE FOR INTERACTIVE PROBLEMS
cout.tie(nullptr); //
#ifdef HELL_JUDGE
auto INITIAL_TIME = high_resolution_clock::now();
#endif
int n , m; cin >> n >> m;
dist.assign(n+1 , INT_MAX);
graph.resize(n+1);
for(int i=0;i<m;++i){
int x,y; cin >> x >> y;
graph.at(x).emplace_back(make_pair(y,0));
graph.at(y).emplace_back(make_pair(x,1));
}
dij(1 , n);
if(dist[n] == INT_MAX){
cout << -1 << '\n';
}else{
cout << dist[n] << '\n';
}
#ifdef HELL_JUDGE
auto FINAL_TIME = high_resolution_clock::now();
cout << "Time : "
<< duration_cast<milliseconds>(FINAL_TIME-INITIAL_TIME).count()
<< " ms" << '\n';
#endif
return 0;
}
This is the solution which will give TLE ( not WA as u scan “n” edges before instead of “m”)
I’m really f**ked up today. But why it shows accepted there, If i read input wrong.
Bro may be in most of cases n = m .
i got tle. Sorry.
Try with 0-1 BFS . It will AC
no i got ac with this one.
// Author : Amit Kumar
#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;
#define int int64_t
vector<vector<pair<int,int>>>graph;
vector<int>dist;
void dij(int start , int End){
priority_queue<pair<int,int> , vector<pair<int,int>> , greater<pair<int,int>>>pq;
pq.push(make_pair(0 , start));
dist[start] =0;
while(!pq.empty()){
int cost = pq.top().first;
int node = pq.top().second; pq.pop();
for(auto&itr:graph[node]){
if(dist[itr.first] > itr.second + dist[node]){
dist[itr.first] = itr.second + dist[node];
pq.push(make_pair(dist[itr.first] , itr.first));
}
}
}
}
signed main(void){
srand(time(NULL));
#ifdef HELL_JUDGE
freopen("input","r",stdin);
freopen("output","w",stdout);
freopen("error","w",stderr);
#endif
ios::sync_with_stdio(false); // FLUSH THE STREAM IF USING puts / printf / scanf/
cin.tie(nullptr); // DISABLE FOR INTERACTIVE PROBLEMS
cout.tie(nullptr); //
#ifdef HELL_JUDGE
auto INITIAL_TIME = high_resolution_clock::now();
#endif
int n , m; cin >> n >> m;
dist.assign(n+1 , INT_MAX);
graph.resize(n+1);
int z;
if(rand()%2){
z = n;
}else{
z = m;
}
for(int i=0;i<z;++i){
int x,y; cin >> x >> y;
graph.at(x).emplace_back(make_pair(y,0));
graph.at(y).emplace_back(make_pair(x,1));
}
dij(1 , n);
if(dist[n] == INT_MAX){
cout << -1 << '\n';
}else{
cout << dist[n] << '\n';
}
#ifdef HELL_JUDGE
auto FINAL_TIME = high_resolution_clock::now();
cout << "Time : "
<< duration_cast<milliseconds>(FINAL_TIME-INITIAL_TIME).count()
<< " ms" << '\n';
#endif
return 0;
}WA on test 19 ?
No issues , but today I learnt both dijkistra and 0-1 bfs.
U used rand()%2 may be possible in my case rand() function gives different value.
Yeah i will try it with 0-1 bfs. Actually I’m trying to solve Chef and Dragon question. As in one post @galencolin said that for new ideas you should leave current problem and try another problem for sometime and then get back to the problem you want to solve. So I just give a try to this one.
