cses graph session editorial(incomplete)
Разница между en2 и en3, 2,734 символ(ов) изменены
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">↵
fFor each unvisited '.' cell we have to madke dfs(or bfs)<br>↵
 and keep on coloring the visited nodes.wWe 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">↵
wWe will store the coordinates of a in A and b in B,now we start bfs 
<br>
from a and try to reackh b.
w
 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 .aAt 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">↵
tThe problem is basically connecting the disconnected components.<br>
do dfs on all unvisited node
s and save one node from each <br>
connected component as a head node.
tThen if there are k connected<br>
 components conn
ceect 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">↵
tThis 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">↵
tThe 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 neighbour blackrs 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 ">↵
qQuestion is about finding cycle.wWe will run a dfs an keep vector VIS <br>↵
to keep track of the nodes in the recusion stack.iIf 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 .n Now we will also keep <br>↵
track of which vertex is in recursion track by TILL this will help us to know till where we need to add nodes to cycle.iere 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">↵
yYou have to do a multi source bfs from all the monsters .y You keep track <br>↵
of minimum step a monster can reach a cell in the  GRID matxrix<br>↵
. Then you apply bfs from source and keep track of steps (initially 0)<br>↵
 and go to only those nodes where stepts are less than grid[x][y] means <br>↵
you only go to those cells where you can reach before any monster has arriv<br>↵
has reach
ed there. yYou 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">↵
tThe 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">↵
tThe question is about simple Floyd Warshall Algorithm[Your text to link here...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">↵
lLet 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 wheather there is a path like 1->k->n then ans is zerother 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 floyd warshal 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">↵
what till you do is fFind minimum distance from 1 till starting of edge and minimum distance <br>↵
from end of node till n and add weight/2.
<br>↵
 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">↵
tThis 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 neg
itative 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>↵

Your title here...↵
------------------
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.

История

 
 
 
 
Правки
 
 
  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)