cses graph session editorial(incomplete)
Разница между en5 и en6, 28 символ(ов) изменены
I got bored with solving and wanted to do something which is related to cp and also very fun so i decided to write this tutorial.bare me for my bad English . ↵

### how to solve grid problems↵

<spoiler summary="trick">↵
here is my template to solve grid problems↵

~~~~~↵
 int dx[]={0,0,1,-1};↵
 int dy[]={1,-1,0,0};↵
 string ds="RLDU";↵
 ↵
 int n,m; ↵
 bool possible(int x,int y){↵
  //cout<<n<<" "<<m<<" "<<x<<" "<<y<<" possible"<<endl;↵
 ↵
     return (x<n&&x>=0&&y<m&&y>=0);↵
 }↵
~~~~~↵
here we cand do just x+dx[i],y+dx[i] to move the four <br>↵
directions and ds helps if we want to record path.<br>↵
we can easily extend it to include four diagonals↵

</spoiler>↵




1) counting rooms↵
------------------↵

<spoiler summary="explanation">↵
For each unvisited '.' cell we have to make dfs(or bfs)<br>↵
 and keep on coloring the visited nodes.We keep track number<br>↵
 of dfs by count variable .our answer would be count.↵
</spoiler>↵


<spoiler summary="code">↵
~~~~~↵

void dfs(int x,int y){↵
if(!possible(x,y)||vis[x][y]!=-1||grid[x][y]==0)return ;↵
vis[x][y]=1;↵
int i;↵
fo(i,0,4){↵
int nx=x+dx[i],ny=y+dy[i];↵
dfs(nx,ny);↵
}↵
}↵
   fo(i,0,n){↵
    string s;↵
    cin>>s;↵
    fo(j,0,m){↵
    if(s[j]=='.')grid[i][j]=1;↵
    else grid[i][j]=0;↵
    }↵
   }↵
   int ans=0;↵
   fo(i,0,n){↵
    fo(j,0,m){↵
    if(grid[i][j]==1&&vis[i][j]==-1){↵
    dfs(i,j);↵
    ans++;↵
    }↵
    }↵
   }↵
   cout<<ans<<endl;↵
   ↵
~~~~~↵

</spoiler>↵

2) Labyrinth↵
------------------↵

<spoiler summary="explanation">↵
We will store the coordinates of a and b ,now we start bfs ↵
<br>from a and try to reach b. We will keep a vector FRM and <br>↵
 DIR which will keep track of the cell from which we came here<br>↵
 and what is the direction of that move .At last if b is visited<br>↵
 we will go in reverse order by using FRM and try to recreate the path.↵
</spoiler>↵


<spoiler summary="code">↵
here a,b is coordinate of 'A' and c,d is coordinate of 'B'↵

~~~~~↵

  queue<pii> q;↵
  q.push({a,b});↵
  vii from[n+1][m+1];↵
  from[a][b].pb({0,0});↵
  char ch[n+1][m+1];↵
  while(!q.empty()){↵
   pii p=q.front();↵
   x=p.x;↵
   y=p.y;↵
 ↵
  // cout<<from[x][y][0].x<<" "<<from[x][y][0].y<<" "<<x<<" "<<y<<" : ";↵
   q.pop();↵
   vis[x][y]=1;↵
   if(grid[x][y]==3)break;↵
   fo(i,0,4){↵
int nx=x+dx[i],ny=y+dy[i];↵
//cout<<x<<" "<<dx[i]<<","<<y<<" "<<dy[i]<<endl;↵
if(!possible(nx,ny))continue;↵

 ↵
if(grid[nx][ny]==0||vis[nx][ny]!=-1)continue;↵
//cout<<"("<<nx<<","<<ny<<") ";↵
vis[nx][ny]=1;↵
q.push({nx,ny});↵
from[nx][ny].pb(p);↵
ch[nx][ny]=ds[i];↵
}↵
//cout<<endl;↵
  }↵
  if(vis[c][d]==-1){↵
   cout<<"NO"<<endl;↵
   return 0;↵
  }↵
  else{↵
   cout<<"YES"<<endl;↵
   pii p={c,d};↵
   while(p.x!=a||p.y!=b){↵
   s+=ch[p.x][p.y];↵
   p=from[p.x][p.y][0];↵
   }↵
   reverse(all(s));↵
   cout<<s.size()<<endl;↵
   cout<<s<<endl;↵
  }↵

~~~~~↵



</spoiler>↵

3) Building Roads↵
------------------↵

<spoiler summary="explanation">↵
The problem is basically connecting the disconnected components.<br>↵
do dfs on all unvisited nodes and save one node from each <br>↵
connected component as a head node.Then if there are k connected<br>↵
 components connect their head node via k-1 edges between heads.<br>↵

</spoiler>↵


<spoiler summary="code">↵

~~~~~↵

   vi v;↵
   fo(i,1,n+1){↵
    if(vis[i]==-1){↵
    v.pb(i);↵
    dfs(i);↵
    }↵
   }↵
   cout<<v.size()-1<<endl;↵
   fo(i,1,v.size()){↵
    cout<<v[i]<<" "<<v[i]-1<<endl;↵
 ↵
   }↵

~~~~~↵


</spoiler>↵

4) Message Route↵
------------------↵

<spoiler summary="explanation">↵
This question is similar to Labyrinth ,start a bfs from 1 and <br>↵
also keep vector FRM to know from where the current node is reached <br>↵
and at last if n is visited go in reverse order using FRM to recreate path.↵
</spoiler>↵


<spoiler summary="code">↵

~~~~~↵

   queue<int> q;↵
   q.push(1);↵
   while(!q.empty()){↵
    int p=q.front();↵
    q.pop();↵
    vis[p]=1;↵
    if(p==n)break;↵
    for(int aa:graph[p]){↵
    if(vis[aa]==-1){↵
    from[aa]=p;↵
    vis[aa]=1;↵
    q.push(aa);↵
    }↵
    }↵
   }↵
   vi v;↵
   if(vis[n]==-1){↵
    cout<<"IMPOSSIBLE"<<endl;↵
   }↵
   else{↵
    v.pb(n);↵
    a=n;↵
    while(a!=1){↵
    a=from[a];↵
    v.pb(a);↵
    }↵
    cout<<v.size()<<endl;↵
    rfo(i,v.size()-1,0){↵
    cout<<v[i]<<" ";↵
 ↵
    }↵
   }↵

~~~~~↵


</spoiler>↵

5) Building teams↵
------------------↵

<spoiler summary="explanation">↵
The question is about coloring the bipartite graphs [more about it](https://www.geeksforgeeks.org/bipartite-graph/).↵
<br>we try to color all vertex greedily if vertex is not visited color <br>↵
it white and run dfs . now color all its uncolored neighbors of white vertex <br>↵
black and vice versa and run dfs on them.<br>at last check that each edge has ends with different colors.↵
</spoiler>↵


<spoiler summary="code">↵

~~~~~↵

void dfs(int p,int c){↵
if(vis[p]!=-1){↵
return ;↵
}↵
vis[p]=1;↵
color[p]=c;↵
for(int aa:graph[p]){↵
if(vis[aa]==-1)dfs(aa,1-c);↵
}↵
}↵

   bool ok=true;↵
   _init(vis);↵
   fo(i,1,n){↵
    if(vis[i]==-1){↵
    dfs(i,0);↵
    }↵
   }↵
   fo(i,0,m){↵
    if(color[edges[i].x]==color[edges[i].y]){↵
    ok=false;↵
    break;↵
    }↵
   }↵
  if(!ok){↵
   cout<<"IMPOSSIBLE"<<endl;↵
   return 0;↵
  }↵
  fo(i,1,n+1){↵
   cout<<color[i]+1<<" ";↵
  }↵


~~~~~↵


</spoiler>↵

6) Round Trip↵
------------------↵

<spoiler summary="explanation ">↵
Question is about finding cycle.We will run a dfs an keep vector VIS <br>↵
to keep track of the nodes in the recusion stack.If we are at node p <br>↵
we will run dfs no all of its childs if any of the child is in  recursion<br>↵
 stack we will add this vertex to an array CYCLE . Now we will also keep <br>↵
track of where to end cycle by TILL . If current is equal to TILL return from all dfs's else return TILL↵
</spoiler>↵


<spoiler summary="code">↵

~~~~~↵

int vis[N],from[N],color[N],till;↵
vi v;↵
int  dfs(int p,int c){↵
//cout<<p<<" <<<"<<endl;↵
if(vis[p]!=-1){↵
till=p;↵
v.pb(p);↵
return 1;↵
}↵
vis[p]=1;↵
for(int aa:graph[p]){↵
if(aa==c)continue;↵
int x=dfs(aa,p);↵
//cout<<p<<" "<<aa<<" "<<x<<endl; ↵
if(x==1){↵
v.pb(p);↵
if(till==p){↵
return 2;↵
}↵
else{↵
return 1;↵
}↵
}↵
else if(x==2)return 2;↵
}↵
vis[p]=2;↵
return 0;↵
}↵
 ↵


~~~~~↵


</spoiler>↵

7) Monsters↵
------------------↵

<spoiler summary="explanation">↵
You have to do a multi source bfs from all the monsters . You keep track <br>↵
of minimum step a monster can reach a cell in the  GRID matrix<br>↵
. Then you apply bfs from source and keep track of steps (initially 0)<br>↵
 and go to only those nodes where steps are less than grid[x][y] means <br>↵
you only go to those cells where you can reach before any monster <br>↵
has reached there. You can recreate path using FRM and DIR matrix as I have done in Labyrinth .↵
</spoiler>↵


<spoiler summary="code">↵

~~~~~↵

 ↵
 const int N=1001;↵
int grid[N][N];↵
string maze[N];↵
int vis[N][N];↵
signed main()↵
{↵
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);↵
    int i,j,x;↵
    cin>>n>>m;↵
  string s;↵
  vii mon;↵
  int ax,ay;↵
  fo(i,0,n){↵
  cin>>s;↵
  fo(j,0,m){↵
  maze[i]=s;↵
  if(s[j]=='A'){↵
  ax=i;↵
  ay=j;↵
  }↵
  if(s[j]=='M'){↵
  mon.pb({i,j});↵
  }↵
  }↵
  }↵
  queue<pair<int,pii>> q;↵
  _init(vis);↵
 ↵
  fo(i,0,mon.size()){↵
  q.push({0,{mon[i].x,mon[i].y}});↵
  vis[mon[i].x][mon[i].y]=1;↵
  }↵
_init(grid);↵
  while(q.size()>0){↵
  pii p=q.front().y;↵
  int lvl=q.front().x;↵
  q.pop();↵
  grid[p.x][p.y]=lvl;↵
  fo(i,0,4){↵
  int nx=p.x+dx[i],ny=p.y+dy[i];↵
  if(!possible(nx,ny))continue;↵
  if(maze[nx][ny]=='#')continue;↵
  if(vis[nx][ny]!=-1)continue;↵
  q.push({lvl+1,{nx,ny}});↵
  vis[nx][ny]=1;↵
 ↵
  }↵
  }↵
  /*↵
  fo(i,0,n){↵
  fo(j,0,m){↵
  cout<<grid[i][j]<<" ";↵
  }↵
  cout<<endl;↵
  }↵
  cout.flush();↵
  */↵
  _init(vis);↵
  pair<int,int> from[n+1][m+1];↵
  char dir[n+1][m+1];↵
  s="RLDU";↵
  q.push({0,{ax,ay}});↵
  pii to={-1,-1};↵
  bool mm=mon.size()>0;↵
  while(q.size()>0){↵
  pii p=q.front().y;↵
  int lvl=q.front().x;↵
  q.pop();↵
  if(grid[p.x][p.y]!=-1&&lvl>=grid[p.x][p.y]){↵
  //cout<<p.x<<" "<<p.y<<" "<<lvl<<" "<<grid[p.x][p.y]<<endl;↵
  continue;↵
  }↵
  ↵
  //cout<<p.x<<" "<<p.y<<":";↵
  if(p.x==0||p.x==n-1||p.y==0||p.y==m-1){↵
  to={p.x,p.y};↵
  break;↵
  }↵
  fo(i,0,4){↵
  int nx=p.x+dx[i],ny=p.y+dy[i];↵
  if(!possible(nx,ny))continue;↵
  if(maze[nx][ny]=='#')continue;↵
  if(vis[nx][ny]!=-1)continue;↵
  if(grid[nx][ny]!=-1&&grid[nx][ny]<=lvl)continue;↵
  from[nx][ny]=p;↵
  q.push({lvl+1,{nx,ny}});↵
  vis[nx][ny]=1;↵
  dir[nx][ny]=s[i];↵
  //cout<<"("<<nx<<","<<ny<<") ";↵
 ↵
  if(nx==0||nx==n-1||ny==0||ny==m-1){↵
  //cout<<lvl<<" "<<↵
 ↵
  to={nx,ny};↵
  break;↵
  }↵
  }↵
 ↵
  if(to.x!=-1)break;↵
//cout<<endl;↵
 ↵
  }↵
 // cout<<to.x<<" "<<to.y<<" "<<ax<<" "<<ay<<endl;↵
  if(to.x==-1){↵
  cout<<"NO"<<endl;↵
  return 0;↵
  }↵
    cout<<"YES"<<endl;↵
    s="";↵
    while(to.x!=ax||to.y!=ay){↵
     s+=dir[to.x][to.y];↵
     //cout<<to.x<<" "<<to.y ↵
     to=from[to.x][to.y];↵
 ↵
 ↵
    }↵
    reverse(all(s));↵
    cout<<s.size()<<endl;↵
    cout<<s<<endl;↵
 ↵
    ↵
    return 0;↵
}↵


~~~~~↵


</spoiler>↵

8) Shortest Routes I↵
------------------↵

<spoiler summary="explanation">↵
The question ask you to implement simple dijsktra [more about it](https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/http://)↵
</spoiler>↵


<spoiler summary="code">↵

~~~~~↵

    priority_queue<pii,vii,greater<pii>> q;↵
    q.push({0,1});↵
    _init(dis);↵
    _init(vis);↵
    dis[1]=0;↵
    while(!q.empty()){↵
     pii p=q.top();↵
     q.pop();↵
     int node=p.y,d=p.x;↵
 ↵
     if(vis[node]!=-1)continue;↵
     vis[node]=1;↵
     for(pii aa:graph[node]){↵
     if(vis[aa.y]!=-1)continue;↵
     if(dis[aa.y]==-1||dis[aa.y]>d+aa.x){↵
     dis[aa.y]=d+aa.x;↵
     q.push({d+aa.x,aa.y});↵
     }↵
     }↵
 ↵
    }↵
    fo(i,1,n+1){↵
     cout<<dis[i]<<" ";↵
    }↵

~~~~~↵


</spoiler>↵

9) Shortest Routes II↵
------------------↵

<spoiler summary="explanation">↵
The question is about simple Floyd Warshall Algorithm[more about it](https://www.geeksforgeeks.org/floyd-warshall-algorithm-dp-16/)↵
</spoiler>↵


<spoiler summary="code">↵

~~~~~↵

    cin>>n>>m>>q;↵
    fo(i,1,n+1){↵
     fo(j,1,n+1){↵
     mat[i][j]=inf;↵
     }↵
     mat[i][i]=0;↵
    }↵
    fo(i,0,m){↵
     cin>>a>>b>>c;↵
     mat[a][b]=min(mat[a][b],c);↵
     mat[b][a]=min(mat[b][a],c);↵
     ↵
    }↵
    int k;↵
    fo(k,1,n+1){↵
     fo(i,1,n+1){↵
     fo(j,1,n+1){↵
     mat[i][j]=min(mat[i][j],mat[i][k]+mat[k][j]);↵
     }↵
     }↵
    }↵
    fo(i,0,q){↵
     cin>>a>>b;↵
 ↵
     cout<<((mat[a][b]>=inf)?-1:mat[a][b])<<"\n";↵
    }↵


~~~~~↵


</spoiler>↵

10) High scores↵
------------------↵

<spoiler summary="explanation">↵
Let say we are at node k we have to find weather there is a positive cycle ending<br>↵
 at k and if there if a cycle whether there is a path like 1->k->n then ans is zero. <br>↵
You can do this by runnig dfs for each node and see if there is cycle ending at <br>↵
that node with positive sum.if there is no such cycle you have to find biggest <br>↵
route from 1 to n. You can do this by using bellman ford complexity o(n*m) ↵
</spoiler>↵


<spoiler summary="code">↵

~~~~~↵

 const int N=2501;↵
 vii graph[N];↵
 int vis[N],dis[N],from1[N],to1[N],fromn[N],ton[N],cycle[N];↵
 int n,m,r,has1,hasn;↵
int findc(int p){↵
vis[p]=1;↵
if(p==1){↵
has1=1;↵
}↵
if(p==n){↵
hasn=1;↵
}↵
for(pii aa:graph[p]){↵
 ↵
if(aa.x==r){↵
dis[p]=max(dis[p],aa.y);↵
continue;↵
}↵
if(vis[aa.x]==1)continue;↵
if(vis[aa.x]==2){↵
dis[p]=max(dis[p],dis[aa.x]+aa.y);↵
}↵
else{↵
int x=findc(aa.x);↵
if(x!=-inf){↵
dis[p]=max(dis[p],x+aa.y);↵
}↵
}↵
 ↵
}↵
 ↵
 ↵
 ↵
 ↵
vis[p]=2;↵
return dis[p];↵
}↵

signed main()↵
{↵
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);↵
    int i,j,x;↵
  cin>>n>>m;↵
  int a,b,c;↵
  fo(i,0,m){↵
  cin>>a>>b>>c;↵
  graph[a].pb({b,c});↵
  }↵
 ↵
  fo(i,1,n+1){↵
  _init(vis);↵
  _init(dis);↵
  has1=0;↵
  hasn=0;↵
  r=i;↵
  fo(j,0,n)dis[j+1]=-inf;↵
  x=findc(i);↵
  //cout<<x<<" "<<has1<<" "<<hasn<<endl;;↵
  to1[i]=has1;↵
  ton[i]=hasn;↵
  cycle[i]=x>0;↵
  if(i==1){↵
  fo(j,0,n)from1[j+1]=vis[j+1];↵
  }↵
  if(i==n){↵
  fo(j,0,n)fromn[j+1]=vis[j+1];↵
  }↵
  }↵
  fo(i,1,n+1){↵
  if(cycle[i]){↵
  if(from1[i]>0&&ton[i]>0){↵
  cout<<-1;↵
  return 0;↵
  }↵
  else if(fromn[i]>0&&to1[i]>0){↵
  cout<<-1;↵
  return 0;↵
  }↵
  }↵
  }↵
  //cout<<endl;↵
  fo(i,0,n)dis[i+1]=-inf;↵
    dis[1]=0;↵
    fo(i,1,n+1){↵
     fo(j,1,n+1){↵
     if(dis[j]==-inf)continue;↵
     for(pii aa:graph[j]){↵
     dis[aa.x]=max(dis[aa.x],dis[j]+aa.y);↵
     }↵
     }↵
    }↵
    cout<<dis[n]<<endl;↵
    ↵
    return 0;↵
}↵

~~~~~↵


</spoiler>↵

11) Flight Discounts↵
------------------↵

<spoiler summary="explanation">↵
Find minimum distance from 1 till starting of edge and minimum distance <br>↵
from end of node till n and add weight/2. may be the concept involved here <br>↵
is called meet in the middle not sure though.create two graphs original and reverse.<br>↵
from original graph start dijkstra from 1 and store result in FRM1 and from <br>↵
reverse graph start dijkstra from n and store result in TON .then iterate <br>↵
through all edges and ans is minimum of (FRM1[edge[i].start + edge.weight/2 + TON[edge.end])↵

</spoiler>↵


<spoiler summary="code">↵

~~~~~↵

  _init(vis);↵
  _init(dis);↵
  dis[0]=0;↵
  priority_queue<pii,vii,greater<pii>> q;↵
  q.push({0,0});↵
  while(!q.empty()){↵
  pii p=q.top();↵
  q.pop();↵
  if(vis[p.y]!=-1)continue;↵
  vis[p.y]=1;↵
 ↵
  for(pii aa:graph[p.y]){↵
  if(vis[aa.x]!=-1)continue;↵
  if(dis[aa.x]==-1||dis[aa.x]>p.x+aa.y){↵
  q.push({p.x+aa.y,aa.x});↵
  dis[aa.x]=p.x+aa.y;↵
  }↵
  }↵
  }↵
  vi f1;↵
  fo(i,0,n){↵
  f1.pb(dis[i]);↵
  }↵
 ↵
 ↵
  _init(vis);↵
  _init(dis);↵
  dis[n-1]=0;↵
//pl();↵
  q.push({0,n-1});↵
  while(!q.empty()){↵
  pii p=q.top();↵
  q.pop();↵
  if(vis[p.y]!=-1)continue;↵
  vis[p.y]=1;↵
  //cout<<p.x<<" "<<p.y<<endl;↵
  for(pii aa:rev[p.y]){↵
  if(vis[aa.x]!=-1)continue;↵
  if(dis[aa.x]==-1||dis[aa.x]>p.x+aa.y){↵
  q.push({p.x+aa.y,aa.x});↵
  dis[aa.x]=p.x+aa.y;↵
  }↵
  }↵
  }↵
 // pl();↵
  vi fn;↵
  fo(i,0,n){↵
  fn.pb(dis[i]);↵
  }↵
  //cout<<f1<<endl;↵
  //cout<<fn<<endl;↵
  int ans=f1[n-1];↵
  for(piii bb:edges){↵
  pii aa=bb.y;↵
 ↵
  if(f1[aa.x]!=-1&&fn[aa.y]!=-1){↵
  ans=min(ans,f1[aa.x]+fn[aa.y]+bb.x/2);↵
  }↵
  ↵
  ↵
  }↵
    cout<<ans<<endl;↵


~~~~~↵


</spoiler>↵

12)Finding Cycles↵
------------------↵

<spoiler summary="explanation">↵
This problem can be solved using bellman ford algorithm .↵
<br>↵
the key idea is relax each edge n(number of node) times if there is no negative cycle <br>↵
then because you should have  got the final answer in n-1 iterations itself<br>↵
which means if there is a negative cycle only then there will be some changes in nth iteration<br>↵
so this way you can detect the cycle and you can regenerate if using FRM array <br>↵
[in depht explanation](https://cp-algorithms.com/graph/finding-negative-cycle-in-graph.html)↵

</spoiler>↵


<spoiler summary="code">↵

~~~~~↵

    cin>>n>>m;↵
    int a,b,c;↵
    fo(i,0,m){↵
     cin>>a>>b>>c;↵
     graph[a].pb({b,c});↵
    }↵
    fo(i,1,n+1)dis[i]=inf;↵
    dis[1]=0;↵
    vi baap(n+1,-1);↵
    fo(i,0,n+1){↵
     till=-1;↵
     fo(j,1,n+1){↵
     for(pii p:graph[j]){↵
     if(dis[p.x]>dis[j]+p.y){↵
     dis[p.x]=dis[j]+p.y;↵
     baap[p.x]=j;↵
     till=p.x;↵
     }↵
     }↵
     }↵
    }↵
  ↵
 ↵
  if(till==-1){↵
  cout<<"NO"<<endl;↵
  return 0;↵
 ↵
  }↵
 ↵
 ↵
  cout<<"YES"<<endl;↵
  fo(i,0,n){↵
  till=baap[till];↵
  }↵
  vi cyc;↵
 ↵
  for(int aa=till;;aa=baap[aa]){↵
  ↵
  cyc.pb(aa);↵
  if(cyc.size()>1&&aa==till){↵
  break;↵
  }↵
  }↵
  reverse(all(cyc));↵
  cout<<cyc<<endl;↵
    ↵
    ↵

~~~~~↵


</spoiler>↵

13) Flight Routes↵
------------------↵

<spoiler summary="explanation ">↵
Important observaion here is k is very small (k<10) and<br>↵
if you want to find k routes each vertex is visited atmax k times in k routes.<br>↵
so it is someting like dijkstra you keep CNT array were you keep count of each node<br>↵
and take a min heap(set or priority queue in cpp) and insert 1st node with cost 0<br>↵
in it. Now let say p is smallest node in heap. increase count of p in CNT array<br>↵
if it is more than k then continue to next iteration.if p is last node add cost <br>↵
to ANS array.now iterate through all edges of p and add child with cost p.cost + edge weight<br>↵
in the heap.↵
<br> now just print ans array complexity o(
nmk).[more about it](https://en.wikipedia.org/wiki/K_shortest_path_routing)↵
</spoiler>↵


<spoiler summary="code">↵

~~~~~↵

 const int N=1e5+5;↵
vii graph[N];↵
 int dis[N],vis[N];↵
signed main()↵
{↵
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);↵
   int i,j,x,n,m,k;↵
   cin>>n>>m>>k;↵
   int a,b,c;↵
   fo(i,0,m){↵
    cin>>a>>b>>c;a--;b--;↵
    graph[a].pb({b,c});↵
 ↵
   }↵
   priority_queue<pii,vii,greater<pii>> q;↵
   _init(dis);↵
   _init(vis);↵
   dis[0]=0;↵
   q.push({0,0});↵
   while(!q.empty()){↵
    pii p=q.top();↵
    q.pop();↵
    if(vis[p.y]==1)continue;↵
    vis[p.y]=1;↵
    for(auto aa:graph[p.y]){↵
    if(vis[aa.x]==-1){↵
    if(dis[aa.x]==-1||dis[aa.x]>aa.y+p.x){↵
    dis[aa.x]=aa.y+p.x;↵
    q.push({dis[aa.x],aa.x});↵
    }↵
    }↵
    }↵
   }↵
  /* fo(i,0,n){↵
    cout<<dis[i]<<" ";↵
   }*/↵
   int count[n+1];↵
   _init0(count);↵
   vi v;↵
   q.push({0,0});↵
   int cnt=k;↵
   while(!q.empty()&&count[n-1]<k){↵
    pii p=q.top();↵
    q.pop();↵
    count[p.y]++;↵
    if(p.y==n-1){↵
    v.pb(p.x);↵
    }↵
    if(count[p.y]<=k){↵
    for(auto aa:graph[p.y]){↵
    q.push({p.x+aa.y,aa.x});↵
    }↵
    }↵
 ↵
   }↵
   sort(all(v));↵
   cout<<v<<endl;↵
   ↵
   ↵
    return 0;↵
}↵
 ↵

~~~~~↵


</spoiler>↵

14) round trip 2↵
------------------↵

<spoiler summary="explanation">↵
The quesiton is about finding cycle in a directed graph. there are 3 types of vertex in dfs<br>↵
color 1: white = the vertex is completely unvisited.<br>↵
color 2: grey = the vertex whose some but not all child are visited.<br>↵
color 3: black = the vertex whose all the child are visited .<br>↵
Now there will be a cycle only when the vertex you are currently on has a grey child.<br>↵
<br>↵
So how will trace the cycle .we can do it by storing the end grey vertex in a variable.<br>↵
and add all the vertex when going back in the recursion until that grey vertex is again  visited.<br>↵
more about it<br>↵
[detecting cycle in directed graph(video)](https://www.youtube.com/watch?v=rKQaZuoUR4M)↵
<br>↵
[detecting cycle in directed graph gfg](https://www.geeksforgeeks.org/detect-cycle-in-a-graph/)↵
<br>↵

</spoiler>↵


<spoiler summary="code">↵

~~~~~↵

int dfs(int p){↵
if(vis[p]!=-1)return 0;↵
vis[p]=1;↵
int x;↵
for(int aa:graph[p]){↵
if(vis[aa]==-1){↵
x=dfs(aa);↵
if(x!=0){↵
if(x==2)return x;↵
cycle.pb(p);↵
if(p==till)return 2;↵
else return 1;↵
} ↵
}↵
else if(vis[aa]==1){↵
cycle.pb(aa);↵
cycle.pb(p);↵
till=aa;↵
return 1;↵
}↵

}↵
vis[p]=2;↵
return 0;↵
}↵
 ↵
 ↵
 ↵
signed main()↵
{↵
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);↵
   int i,j,x,n,m;↵
   cin>>n>>m;↵
   int a,b;↵
   fo(i,0,m){↵
    cin>>a>>b;↵
    graph[a].pb(b);↵
   }↵
   _init(vis);↵
   fo(i,1,n+1){↵
    if(vis[i]==-1){↵
    dfs(i);↵
    }↵
    if(cycle.size()>0)break;↵
   }↵
   ↵
   if(cycle.size()==0){↵
    cout<<"IMPOSSIBLE"<<endl;↵
   }↵
   else{↵
    cout<<cycle.size()<<endl;↵
    reverse(all(cycle));↵
    cout<<cycle<<endl;↵
   }↵
   ↵
   ↵
    return 0;↵
}↵


~~~~~↵


</spoiler>↵


15) Course Schedule↵
------------------↵

<spoiler summary="explanation">↵
the problem is about simple topological sort.<br>↵
more about it<br>↵
[topsort video](https://www.youtube.com/watch?v=ddTC4Zovtbc)<br>↵
[topsort tutorial cp algo](https://cp-algorithms.com/graph/topological-sort.html)<br>↵
</spoiler>↵


<spoiler summary="code">↵

~~~~~↵

 const int N=1e5+5;↵
 ↵
vi graph[N],top;↵
int vis[N],till;↵
 bool cycle;↵
void dfs(int p){↵
if(vis[p]!=-1)return ;↵
vis[p]=1;↵
int x;↵
for(int aa:graph[p]){↵
if(vis[aa]==1){↵
cycle=true;↵
}↵
else if(vis[aa]==-1){↵
dfs(aa);↵
}↵
if(cycle)return;↵
}↵
 ↵
vis[p]=2;↵
top.pb(p);↵
return ;↵
}↵
 ↵
 ↵
 ↵
signed main()↵
{↵
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);↵
   int i,j,x,n,m;↵
   cin>>n>>m;↵
   int a,b;↵
   fo(i,0,m){↵
    cin>>a>>b;↵
    graph[a].pb(b);↵
   }↵
   cycle=0;↵
   _init(vis);↵
   fo(i,1,n+1){↵
    if(vis[i]==-1){↵
    dfs(i);↵
    }↵
    if(cycle)break;↵
   }↵
   ↵
   if(cycle){↵
    cout<<"IMPOSSIBLE"<<endl;↵
   }↵
   else{↵
    ↵
    reverse(all(top));↵
    cout<<top<<endl;↵
   }↵
   ↵
   ↵
    return 0;↵
}↵
 ↵

~~~~~↵


</spoiler>↵

16) Longest flight routes↵
------------------↵

<spoiler summary="Explanation">↵
I solved this problem using dp. Here there is no cycle so there could not be an infinite path.<br>↵
What we can do if there is a path like A->B . we find maxpath <br>↵
for a by just adding 1 to max path of b. `dp[a]=max(dp[a],dp[b]+1)`<br>↵
</spoiler>↵


<spoiler summary="code">↵

~~~~~↵

int dfs(int p){↵

vis[p]=1;↵
int x;↵
if(p==n){wt[p]=0;vis[p]=2;return 0;}↵
for(int aa:graph[p]){↵

 if(vis[aa]==-1){↵
dfs(aa);↵
 ↵
}↵
if(wt[aa]==-1)continue;↵
 ↵
if(wt[aa]+1>wt[p]){↵
//cout<<p<<" "<<aa<<" "<<wt[aa]<<" "<<wt[p]<<" "; ↵
wt[p]=wt[aa]+1;↵
to[p]=aa;↵
// cout<<wt[p]<<endl;↵
}↵

}↵
 ↵
 ↵
vis[p]=2;↵

return wt[p];↵
}↵
 ↵

~~~~~↵


</spoiler>↵

17) Game Routes↵
------------------↵

<spoiler summary="Explanation">↵
this question is about dp on graph.the number of ways <br>↵
by which a node A can reach N is equal to sum of ways of its childs.<br>↵
`for(int child:graph[a])dp[a]=(dp[a]+dp[child])%MOD`↵
</spoiler>↵


<spoiler summary="code">↵

~~~~~↵

int dfs(int p){↵

vis[p]=1;↵
int x;↵
if(p==n){wt[p]=1;vis[p]=2;return 0;}↵
for(int aa:graph[p]){↵

 if(vis[aa]==-1){↵
dfs(aa);↵
 ↵
}↵
wt[p]+=wt[aa];↵
wt[p]%=MOD;↵

}↵
 ↵
 ↵
vis[p]=2;↵

return wt[p];↵
}↵
 ↵

~~~~~↵

</spoiler>↵

18) Investigation↵
------------------↵

<spoiler summary="Explanation">↵
The question is basically dijkstra + dp.<br>↵
You have to run dijkstra and keep track of minimum distance from 1 of all vertex.<br>↵
If a child has minimum distance = current dis+ edge.weight you just updated the dp.<br>↵
If a child has min dis>current dis+ edge.weight you reset everyting in dp.<br>↵
</spoiler>↵


<spoiler summary="code">↵

~~~~~↵

signed main()↵
{↵
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);↵
   int i,j,x;↵
   cin>>n>>m;↵
   int a,b,c;↵
   fo(i,0,m){↵
    cin>>a>>b>>c;↵
    graph[a].pb({b,c});↵
   }↵
   _init(vis);↵
   _init(min_price);↵
   _init0(routes);↵
   _init(min_flight);↵
   _init(max_flight);↵
   _init(can_reachn);↵
   ↵
   min_price[1]=0;↵
   routes[1]=1;↵
   min_flight[1]=0;↵
   max_flight[1]=0;↵
   priority_queue<pii,vii,greater<pii>> q;↵
   q.push({0,1});↵
   while(!q.empty()){↵
    x=q.top().y;↵
    q.pop();↵
    if(vis[x]!=-1)continue;↵
    vis[x]=1;↵
    for(pii aa:graph[x]){↵
    if(vis[aa.x]==1)continue;↵
    if(min_price[aa.x]==-1||min_price[aa.x]>min_price[x]+aa.y){↵
    min_price[aa.x]=min_price[x]+aa.y;↵
routes[aa.x]=routes[x];↵
min_flight[aa.x]=min_flight[x]+1;↵
max_flight[aa.x]=max_flight[x]+1;↵
q.push({min_price[aa.x],aa.x});↵
    }↵
    else if(min_price[aa.x]==min_price[x]+aa.y){↵
    routes[aa.x]+=routes[x];↵
routes[aa.x]%=MOD;↵
min_flight[aa.x]=min(min_flight[aa.x],min_flight[x]+1);↵
max_flight[aa.x]=max(max_flight[aa.x],max_flight[x]+1);↵
q.push({min_price[aa.x],aa.x}); ↵
    }↵
 ↵
    }↵
 ↵
   }↵
 ↵
 ↵
 ↵
 ↵
   cout<<min_price[n]<<" "<<routes[n]<<" "<<min_flight[n]<<" "<<max_flight[n]<<endl;↵
 ↵
   ↵
   ↵
    return 0;↵
}↵

~~~~~↵


</spoiler>↵

19) Planet queries I↵
------------------↵

<spoiler summary="explanation">↵
basically tunnel is directed edge and left end is parent and right end is first order child(its direct child).<br>↵
moving k steps in tunnel means you have to go to kth order child .you can do this using binary lifting.<br>↵

<br>↵
here is short explanation of binary lifting.<br>↵
basically we keep tack of all the childs of a node which is at a distance which is power of 2.<br>↵
if a graph is like this a->b->c->d->e<br>↵
then first order child of a is b (1st child)<br>↵
second order child of a is c (2nd child)<br>↵
and third order child of a is e(4th child)<br>↵
so by doing this we can find the kth child in log n time .<br>↵
more about it.<br>↵
[binary lifting cp algo](https://cp-algorithms.com/graph/lca_binary_lifting.html)<br>↵
[binary lifting algo live](https://www.youtube.com/watch?v=kOfa6t8WnbI)<br>↵
</spoiler>↵


<spoiler summary="code">↵

~~~~~↵

   cin>>n>>q;↵
   fo(i,1,n+1){↵
    cin>>x;↵
    dp[0][i]=x;↵
   }↵
   fo(i,1,LOGN){↵
    fo(j,1,n+1){↵
    dp[i][j]=dp[i-1][dp[i-1][j]];↵
    //cout<<dp[i-1][j]<<" ";↵
    }↵
   // cout<<endl;↵
   }↵
   ↵
   fo(i,0,q){↵
    int a,b;↵
    cin>>a>>b;↵
    rfo(j,30,0){↵
    //cout<<(b&(1ll<<j))<<" ";↵
    if((b&(1ll<<j))>0){↵
    a=dp[j][a];↵
    }↵
    }↵
    cout<<a<<endl;↵
   }↵
   ↵
   ↵

~~~~~↵


</spoiler>↵

#### other useful links↵

<spoiler summary="links">↵
[detecting cycle in directed graph(video)](https://www.youtube.com/watch?v=rKQaZuoUR4M)↵
<br>↵
[detecting cycle in directed graph gfg](https://www.geeksforgeeks.org/detect-cycle-in-a-graph/)↵
<br>↵
[topsort video](https://www.youtube.com/watch?v=ddTC4Zovtbc)<br>↵
[topsort tutorial cp algo](https://cp-algorithms.com/graph/topological-sort.html)<br>↵
[binary lifting cp algo](https://cp-algorithms.com/graph/lca_binary_lifting.html)<br>↵
[binary lifting algo live](https://www.youtube.com/watch?v=kOfa6t8WnbI)<br>↵
</spoiler>↵




<br>↵

Hope this is helpfull to you . I will try to add more as I solve furthure.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский arham_doshi 2021-02-11 11:04:59 0 (published)
en6 Английский arham_doshi 2020-07-17 07:40:44 28 Tiny change: 'plexity o(nmk).[more ' -> 'plexity o(mk).[more '
en5 Английский arham_doshi 2020-07-01 11:04:56 8040
en4 Английский arham_doshi 2020-06-30 16:28:03 23 Tiny change: ' by using floyd warshal complexit' -> ' by using bellman ford complexit'
en3 Английский arham_doshi 2020-06-30 09:23:47 2734 (published)
en2 Английский arham_doshi 2020-06-29 19:13:30 16645
en1 Английский arham_doshi 2020-06-29 16:47:49 801 Initial revision (saved to drafts)