ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1930. Ivan's Car

I will just post the soution because i want to ruin it for you ;)
Posted by Ishan Pandey 18 Mar 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

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
{
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;
}
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;
}