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 usingfloyd warshalbellman 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>↵
↵
<br>↵
Hope this is helpfull to you . I will try to add more as I solve furthure.
↵
### 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
</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>↵
↵
<br>↵
Hope this is helpfull to you . I will try to add more as I solve furthure.
