#include <bits/stdc++.h>
using namespace std;


 
#define int         long long
#define double      long double
#define pb          push_back
#define pf          push_front
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define all(a)      (a).begin(),(a).end()
#define rall(a)     (a).rbegin(),(a).rend()
#define x           first
#define y           second
#define endl        '\n'
#define sz(x)     (int)(x).size()

#define fo(i,l,u)   for(i=l;i<u;i++)
#define rfo(i,l,u)  for(i=l;i>=u;i--)
#define allfo(s)    for(auto it=(s).begin();it!=(s).end();it++)


struct segtree{
  vi tree,laz,laz1,change1,change;
  int n,base;
  void began(int z){
      int x,i;
      n=z;
      //initialise everythin with zero
      fo(i,0,2*n+5){
          tree.pb(0);
          laz.pb(0);
          laz1.pb(0);
          change1.pb(0);
          change.pb(0);
      }
    
  }
  //laz is for increment query
  //laz1 is for update query

  void lazy_up(int p,int l,int r){
      if(l>r)return ;
       if(change[p]!=0){
      
          tree[p]+=laz[p]*(r-l+1);
          if(l!=r){
          
              laz[2*p]+=laz[p];
              laz[2*p+1]+=laz[p];
              laz1[2*p]=0;
              laz1[2*p+1]=0;
              change[2*p]=1;
              change[2*p+1]=1;
              change1[2*p]=0;
              change1[2*p+1]=0;
          }
            laz[p]=0;
            laz1[p]=0;
            change[p]=0;
            change1[p]=0;

      }
  }

  void lazy_up1(int p,int l,int r){
      if(l>r)return ;
       if(change1[p]!=0){
         
          tree[p]=laz1[p]*(r-l+1);
          if(l!=r){

              laz1[2*p]=laz1[p];
              laz1[2*p+1]=laz1[p];
              laz[2*p]=0;
              laz[2*p+1]=0;
              change[2*p]=0;
              change[2*p+1]=0;
              change1[2*p]=1;
              change1[2*p+1]=1;
                 
          }
            laz[p]=0;
            laz1[p]=0;
            change[p]=0;
            change1[p]=0;
       
      }
  }


  int query(int p,int l,int r,int a,int b){
     if(l>r)return 0;
     lazy_up1(p , l , r );
       lazy_up(p , l , r );
      
      if(l>=a && r<=b){

          return tree[p];
        }
      else if(r<a || l>b)return 0;
      int mid=(l+r)/2;
      int a1,b1;

      a1=query(2*p ,l , mid , a , b);
      b1=query(2*p+1 , mid+1 , r , a , b);

      tree[p]=(tree[2*p]+tree[2*p+1]);
      return a1+b1;
      
  }
  
  void update1(int p,int l,int r,int a,int b,int val){
       lazy_up1(p , l , r );
       lazy_up(p , l , r );
       

        
        if(l>=a && r<=b){
            tree[p]=val*(r-l+1);
        

           
            if(l!=r){
                laz1[2*p]=val;
                laz1[2*p+1]=val;
                laz[2*p]=0;
                laz[2*p+1]=0;
              change[2*p]=0;
              change[2*p+1]=0;
              change1[2*p]=1;
              change1[2*p+1]=1;
            }
            
        }
        else if(r<a||l>b){
            return ;
        }
        else{
            int mid=(l+r)/2;
         int a1,b1;

         update1(2*p , l , mid , a , b , val);
         update1(2*p+1 , mid+1 , r , a , b , val);
         tree[p]=(tree[2*p]+tree[2*p+1]);

           return ;
        }
        
      }


      void update(int p,int l,int r,int a,int b,int val){
       lazy_up1(p , l , r );
       lazy_up(p , l , r );

        
        if(l>=a && r<=b){
            tree[p]+=val*(r-l+1);
        

            if(l!=r){
                laz[2*p]+=val;
                laz[2*p+1]+=val;
                laz1[2*p]=0;
                laz1[2*p+1]=0;
                change[2*p]=1;
              change[2*p+1]=1;
              change1[2*p]=0;
              change1[2*p+1]=0;
            }
            
        }
        else if(r<a || l>b){
            return ;
        }
        else{
            int mid=(l+r)/2;
         int a1,b1;

         update(2*p , l , mid , a , b , val);
         update(2*p+1 , mid+1 , r , a , b , val);
         tree[p]=(tree[2*p]+tree[2*p+1]);

           return ;
        }
        
      }
      
  
  
  int query(int l,int r){

     return query(1 , 1 , n , l , r);
  }
  
  void update(int a,int b,int val){

      update(1 , 1 , n , a , b , val);
  }
  void update1(int a,int b,int val){
     update1(1 , 1 , n , a, b ,  val);
  }
    
};



 
signed main()
{
      ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
     int i,j,x,n,m;
     cin>>n>>m;
     segtree tree;
     tree.began(n);
     fo(i,1,n+1){
      cin>>x;
      tree.update(i , i , x );
     }
     int type,a,b,c;
     fo(i,0,m){
        cin>>type;
        if(type==1){
          cin>>a>>b>>c;
          tree.update(a , b , c);
        }
        else if(type==2){
          cin>>a>>b>>c;
          tree.update1(a , b , c);
        }
        else {
          cin>>a>>b;
          cout<<tree.query(a , b)<<endl;
        }
     }
     
     
     
   
   
    return 0;
}

100 14
7 6 4 6 2 9 4 8 10 4 10 3 7 10 2 9 4 1 7 4 5 9 9 7 9 6 5 10 8 4 7 10 5 3 3 1 6 7 6 1 5 7 7 7 7 2 3 5 10 8 4 8 7 5 8 6 8 6 7 9 3 10 6 6 8 1 5 8 5 9 9 5 8 8 4 6 6 3 1 2 1 2 9 2 10 9 9 6 5 7 9 10 5 8 2 7 4 1 4 7
2 72 77 5
2 56 63 8
3 40 51
2 42 51 5
3 33 35
2 31 97 6
3 88 90
2 38 78 2
3 77 82
1 70 80 9
1 53 81 4
1 86 93 4
2 12 33 1
3 22 64

66
11
18
28
138

66
11
18
28
142

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
directions and ds helps if we want to record path.
we can easily extend it to include four diagonals

For each unvisited '.' cell we have to make dfs(or bfs)
and keep on coloring the visited nodes.We keep track number
of dfs by count variable .our answer would be count.

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;
   

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

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

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

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

This question is similar to Labyrinth ,start a bfs from 1 and
also keep vector FRM to know from where the current node is reached
and at last if n is visited go in reverse order using FRM to recreate path.

   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]<<" ";
 
   	}
   }

The question is about coloring the bipartite graphs more about it.
we try to color all vertex greedily if vertex is not visited color
it white and run dfs . now color all its uncolored neighbors of white vertex
black and vice versa and run dfs on them.
at last check that each edge has ends with different colors.

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

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

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

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

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

The question ask you to implement simple dijsktra more about it

    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]<<" ";
    }

The question is about simple Floyd Warshall Algorithmmore about it

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

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

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

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

 	_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;

This problem can be solved using bellman ford algorithm .
the key idea is relax each edge n(number of node) times if there is no negative cycle
then because you should have got the final answer in n-1 iterations itself
which means if there is a negative cycle only then there will be some changes in nth iteration
so this way you can detect the cycle and you can regenerate if using FRM array
in depht explanation

    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;
    
    

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

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

The quesiton is about finding cycle in a directed graph. there are 3 types of vertex in dfs
color 1: white = the vertex is completely unvisited.
color 2: grey = the vertex whose some but not all child are visited.
color 3: black = the vertex whose all the child are visited .
Now there will be a cycle only when the vertex you are currently on has a grey child.

So how will trace the cycle .we can do it by storing the end grey vertex in a variable.
and add all the vertex when going back in the recursion until that grey vertex is again visited.
more about it
detecting cycle in directed graph(video)
detecting cycle in directed graph gfg

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

the problem is about simple topological sort.
more about it
topsort video
topsort tutorial cp algo

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

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

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

this question is about dp on graph.the number of ways
by which a node A can reach N is equal to sum of ways of its childs.
for(int child:graph[a])dp[a]=(dp[a]+dp[child])%MOD

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

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

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

basically tunnel is directed edge and left end is parent and right end is first order child(its direct child).
moving k steps in tunnel means you have to go to kth order child .you can do this using binary lifting.

here is short explanation of binary lifting.
basically we keep tack of all the childs of a node which is at a distance which is power of 2.
if a graph is like this a->b->c->d->e
then first order child of a is b (1st child)
second order child of a is c (2nd child)
and third order child of a is e(4th child)
so by doing this we can find the kth child in log n time .
more about it.
binary lifting cp algo
binary lifting algo live

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

detecting cycle in directed graph(video)
detecting cycle in directed graph gfg
topsort video
topsort tutorial cp algo
binary lifting cp algo
binary lifting algo live