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

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]

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema dmink:

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

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #3422 dmink

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3422 dmink de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #3422 dmink