# PBinfo #4162 – DrumuriMinime – Rezolvare C++

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

## Enunț

Se consideră un graf orientat cu n vârfuri, numerotate de la 1 la n, şi m arce.  Definim distanţa minimă dintre două noduri x şi y ca fiind numărul minim de arce al unui drum elementar care are ca extremitate inițială vârful x și ca extremitate finală vîrful y.

Cerinţa
Se dau k perechi de vârfuri x y. Determinați pentru fiecare pereche distanța minimă dintre x și y.

Date de intrare
Fişierul de intrare dmin2.in conţine pe prima linie două numere n şi m, reprezentând numărul de noduri, respectiv numărul de arce. Fiecare dintre următoarele m linii va conţine câte două numere x şi y, separate printr-un spaţiu, cu semnificaţia: există arc de la nodul x la nodul y.

Următoarea linie conține un număr k, iar următoarele k linii câte două numere x y.

Date de ieşire
Fişierul de ieşire dmin2.out va conţine k linii. Fiecare linie va conține distața minimă dintre nodurile x y din fișierul de intrare, în ordinea din fișierul de intrare. Dacă pentru perechea x y nu există un drum elementar de la x la y, atunci pe linia corespunzătoare se va afișa valoarea -1.

Restricţii şi precizări

n ≤ 100
k ≤ 100

Exemplu:
dmin2.in


6 7
1 3
1 2
2 3
2 4
3 4
4 5
5 6
3
1 6
5 3
2 5
dmin2.out

4
-1
2

## Cod sursă C++

```cpp
#include <fstream>
using namespace std;
ifstream fin("dmin2.in");
ofstream fout("dmin2.out");
int k,n,m,A[101][101],V[101],D[101];
int dist_min(int x, int y)
{
    int Q[101],st=1,dr=1;
    for(int i=1;i<=n;i++)
        V[i]=D[i]=0;
    Q[st]=x;
    V[x]=1;
    D[x]=0;
    while(st<=dr && D[y]==0)
    {
        int v=Q[st];
        for(int i=1;i<=n;i++)
            if(!V[i] && A[v][i]==1)
            {
                dr++;
                Q[dr]=i;
                V[i]=1;
                D[i]=D[v]+1;
            }
        st++;
    }
    if(V[y]) return D[y];
    else return -1;
}
int main()
{
    int x,y;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y;
        A[x][y]=1;
    }
    fin>>k;
    for(int i=1;i<=k;i++)
    {
        fin>>x>>y;
        fout<<dist_min(x,y)<<endl;
    }
    return 0;
}
```

## Resurse

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