This test helped me to find my bug. I modified dijkstra algo and added direction array.
9 12
7 3
9 3
9 2
1 2
1 3
4 7
4 1
5 1
4 8
5 8
6 5
2 6
1 8
Answer:0


Edited by author 31.01.2013 17:37

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
#define mod 1000000007

#define maxn 10010
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define inf 100000000000

vector<pair<int, int>> adj[maxn];
int n, m;

// struct node //for edges
// {
//     int pos, dir, dist;

//     node(){};
//     node(int _pos, int _dir)
//     {
//         pos = _pos;
//         dir = _dir;
//     }
// };

int go(int s, int e)
{

    int dist[maxn][2];
    for(int i=0; i<maxn; i++)
    {
        for(int j=0; j<=1; j++)
        {
            dist[i][j] = inf;
        }
    }

    deque<pair<int, int>> q; //pair->{node, edgedir}

    //making direction list here,
    q.push_back({s, 0}); //0->outgoing to node s
    dist[s][0] = 0;
    q.push_back({s, 1}); //1->incoming from node s
    dist[s][1] = 0;

    while(!q.empty())
    {
        pair<int, int> cur = q.front();
        //node
        int v = cur.first;
        int dir = cur.second;
        //dist
        int dv = dist[v][dir];

        //guarenteed that shortest dist till cur node has been calc already

        q.pop_front();
        //if(dv == inf) break;

        if(cur.first == e) return dv; //gauarenteed via djikstra that this willbe minimest

        //relax all the neighbours, and as you relax one , push into minheap the nodes
        for(auto it: adj[v])
        {
            int to = it.fi;
            int dir2 = it.se;
            //previous
            //note that for type edge dir, you have relax for all neighbouring nodes
            int dist2=0;
            if(dir2 == dir)
            {
                dist2 = dist[v][dir2];
                //dist[to][dir2] = min( dist[to][dir2], dist[v][dir2] );
            }
            else dist2 = dist[v][dir] + 1;
               // dist[to][dir2] = min( dist[to][dir2], dist[v][dir] + 1);


            //only relax and add to queue, if less than prev distance to this node
            if(dist2 < dist[to][dir2])
            {
                if(dist2 <= dv) //less than equal to cur_dist
                    q.push_front({to, dir2});
                else
                    q.push_back({to, dir2});

                dist[to][dir2] = dist2;

            }


        }
    }

    return -1;


}

void solve()
{
    cin>>n>>m;

    for(int i=1;i<=m;i++)
    {
        int x, y; cin>>x>>y;
        adj[x].pb({y, 0});
        adj[y].pb({x, 1});
    }
    int s, e; cin>>s>>e;
    //cout<<"hi";
    int ans = go(s, e);
    cout<<ans<<endl;


}

signed main()
{
    int t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}

:P

please help me.
i have some problems in test 5.
please help me!

try this:
3 2
1 3
2 3
1 2

answear: 1

can someone please provide test #6?

I had maintained dis[n+1][2] for distance. But visited array was vis[n+1], changed it to
vis[n+1][2] and simple bfs.

Easy concept, just to think for a while. AC in one go!

just use bfs as a modified version of dijkstra and you will be done

0-1 bfs on graph with 2 * n verticles.

I am using dijkstra by adding a reverse edge of weight 1. Answer will be MIN ( Shortest distance, total_edges - shortest_distance);

If you are using BFS, use a adjacency list. It's faster for finding the adjacents nodes. You too should use a "direccion list". It has the same size that the adjacency list, but it's filled with boolean values. For example, in the adjacency list of the node 1, you have nodes 2 3 4. If you need to go uphill from 1 to 2, in the correspondant place of the 2, you should write a 1, and if you need to go downhill, a 0. This is how I solved. I was stuck on time limit when I was using the same format of given data, but later I understood that the adjacency list it's very faster than 2 cols matrix (faster, but uses a lot more memory). Good luck, and try all the test posted in discussion.

3 3
1 2
2 3
3 1
1 3
how is this possible?
from 1 to 2 there is an uphill road...from 2 to 3 there is also an uphill road...then how can there be a uphill road from 3 to 1??from 3 to 1 there should be a downhill road...
correct me if i am wrong..

6 6
4 2
1 2
4 5
2 3
2 6
6 4
1 5
answer : 0

Edited by author 07.01.2014 01:25

In this problem I use bfs and Dejikstra, in two cases I got AC, but my solutions are very slowly then others. I can't understand way ?

9 15
1 2
3 1
1 5
4 2
6 2
3 4
3 6
4 5
6 5
5 7
6 7
6 8
8 7
7 9
8 9
1 9

Ans: 0

BFS solution gets accepted.. but it fails in many cases. However the perfect solution to be used is Dijkstra's. The test cases do not contain cases where cycles terminate at nodes in between source and destination.

Could you tell me some useful test, if you had the same problem?! Thanks ^_^

I use BFS, but WA12 :( Help me, pleas give me test

4 3
1 2
2 1
3 2
1 3