# PBinfo #3422 – dmink – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: andrei

## Enunț

Cerința
Se dă un graf orientat cu n vârfuri și m arce prin lista arcelor și un număr natural k.  Afișați vârfurile din graf care se află la distanță k față de vârful 1. Distanța dintre două vârfuri x și y este egală cu k dacă cel mai scurt drum care are ca extremitate inițială pe x și ca extremitate finală pe y are lungimea k sau cel mai scurt drum care are ca extremitate inițială pe y și ca extremitate finală pe x are lungimea k.

Date de intrare
Programul citește de la tastatură numărul n de noduri și numărul m de arce și numărul k, iar apoi lista arcelor, formată din m perechi de forma i j, cu semnificația că există arc  de la nodul i la nodul j.

Date de ieșire
Programul va afișa pe ecran în ordine crescătoare și separate prin câte un spațiu vârfurile din graf care se află la distanță k față de vârful 1. Dacă nu există nici un vârf care să îndeplinească condiția, atunci se va afișa Nu exista.

Restricții și precizări

1 ≤ k ≤ n ≤ 100

Exemplu:
Intrare

8 12 2
1 3
3 5
5 7
7 1
2 6
6 8
8 2
1 4
4 6
4 8
4 2
1 8
Ieșire

2 5 6
Explicație
Drumurile de lungime minimă care au lungimea egală cu 2 și o extremitate în vârful 1 sunt:
[1, 4, 2]
[1, 8, 2]
[1, 3, 5]
[1, 4, 6]
[5, 7, 1]

## Cod sursă C++

```cpp
#include <iostream>
using namespace std;
const int inf=100;
int A[101][101],n,m,k,gasit;
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j) A[i][j]=inf;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        A[x][y]=1;
    }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(A[i][j]>A[i][k]+A[k][j])
                    A[i][j]=A[i][k]+A[k][j];
    for(int i=1;i<=n;i++)
        if(A[1][i]==k || A[i][1]==k)
        {
            cout<<i<<" ";
            gasit=1;
        }
    if(!gasit) cout<<"Nu exista";
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3422)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3422/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3422/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)