ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1930. Машина инженера Ивана

I will just post the soution because i want to ruin it for you ;)
Послано Ishan Pandey 18 мар 2020 10:00
#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;
}
Re: I will just post the soution because i want to ruin it for you ;)
Послано Manan Shah 4 май 2020 20:39
I do not understand the final push back and front part. Why to push only if dist is less than dv? Why are we comparing it to dv?
If it is for the right position in the queue of the pushed element(like in 0-1 bfs),then how do we know that the queue only has 0-1? That is the underlying part of the 0-1 bfs right?else it is dijkstra. I think the queue has difference of 1 between its min and max.
Can you tell what all is true and exactly what is happening.
I would really appreciate.
Thank you

Edited by author 04.05.2020 20:46

Edited by author 04.05.2020 20:47
Re: I will just post the soution because i want to ruin it for you ;)
Послано Tushar Paul 28 мар 2023 23:19
if(dist2 <= dv) //less than equal to cur_dist
                    q.push_front({to, dir2});
                else
                    q.push_back({to, dir2});


CAN YOU EXPLAIN ME THIS PART WHY DIST 2 GREATER IS PUSHED BACK NOT IN FRONT AND VICE VERSA WHAT I MEAN TO KNOW IS WHY WE COMPARE CONNECTED VERTEX DISTANCE