# How can I optimise more Dijikstra's algorithm ? ( graph problem 4)

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 .

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)

2 Likes

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.

This problem is solved using 0-1 BFS.

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.

1 Like

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.

1 Like

@galencolin HERE is my 0_1_BFS solution approach still it gives TLE