Imprimă pagina - [HackerRank] Breadth First Search: Shortest Reach

Problem Statement

Given an undirected graph consisting of N nodes (labelled 1 to N) where a specific given node S represents the start position and an edge between any two nodes is of length 6 units in the graph.

It is required to calculate the shortest distance from start position (Node S) to all of the other nodes in the graph.

Note 1: If a node is unreachable , the distance is assumed as âˆ’1.
Note 2: The length of each edge in the graph is 6 units.

Input Format

The first line contains T, denoting the number of test cases.
First line of each test case has two integers N, denoting the number of nodes in the graph and M, denoting the number of edges in the graph.
The next M lines each consist of two space separated integers x y, where x and y denote the two node between which the edge exists.
The last line has an integer S, denoting the starting position.

Constraints
1â‰¤Tâ‰¤10
2â‰¤Nâ‰¤1000
1â‰¤Mâ‰¤NÃ—(Nâˆ’1)2
1â‰¤x,y,Sâ‰¤N

While performing the traversal, if there are edges between the same pair of nodes with different weights, the last one (most recent) is to be considered as the only edge between them.

Output Format

For each of T test cases, print a single line consisting of Nâˆ’1 space separated integers, denoting the shortest distances of the N-1 nodes from starting position S.

For unreachble nodes, print âˆ’1.

Sample Input

1
4 2
1 2
1 3
1

Sample Output

6 6 -1

The graph given in the test case is shown as :
(http://i1.someimage.com/DlfuXj4.png)
S denotes the node 1 in the test case and B,C and D denote 2,3 and 4. Since S is the starting node and the shortest distances from it are (1 edge, 1 egde, Infinity) to the nodes B,C and D (2,3 and 4) respectively.

Node D is unreachable, hence -1 is printed (not Infinity).

[HackerRank] Breadth First Search: Shortest Reach (https://www.hackerrank.com/challenges/bfsshortreach)

Am fÄƒcut un BFS È™i am memorat distanÈ›a de la S la toate nodurile Ã®ntr-un vector(D). Nu È™tiu dacÄƒ am greÈ™it la implementare, dar nu Ã®nÈ›eleg ce vrea sÄƒ zicÄƒ enunÈ›ul cu observaÈ›ia asta:
While performing the traversal, if there are edges between the same pair of nodes with different weights, the last one (most recent) is to be considered as the only edge between them.

Cod:

# include <stdio.h>
# define NMAX 1001

int T,N,M,S,D[NMAX],Mat[NMAX][NMAX];

struct nod
{
    int x,y;
    struct nod *urm;
};
struct nod *P,*Q;

void Adaug( int x, int y )
{
    struct nod * nou = (struct nod*)malloc(sizeof(struct nod));
    nou->x = x;
    nou->y = y;
    nou->urm = NULL;
    if( P == NULL )
        P = Q = nou;
    else
    {
        Q->urm = nou;
        Q = Q->urm;
    }
}

void Sterg()
{
    struct nod *Z;
    Z = P;
    P = P->urm;
    free(Z);
}

void InitD()
{
    int i;
    for( i = 1 ; i <= N ; ++i )
        D[i] = N*N+1;
    D[S] = 0;
}

void BFS()
{
    int j,NodCurent,Dist;
    Adaug(S,1);
    while( P )
    {
        NodCurent = P->x;
        Dist = P->y*6;
        for( j = 1 ; j <= N ; ++j )
            if( Mat[NodCurent][j] == 1 && D[j] == N*N+1 )
            {
                if( D[j] > Dist )
                    D[j] = Dist;
                Adaug(j,Dist/6+1);
            }
        Sterg();
    }
}

void Tipar()
{
    int i;
    for( i = 1 ; i <= N ; ++i )
    {
        if( i == S )
            continue;
        if( D[i] == N*N+1 )
            D[i] = -1;
        printf("%d ",D[i]);
    }
    putchar('\n');
}

int main()
{
    int i,j,x,y;
    scanf("%d",&T);
    for( i = 1 ; i <= T ; ++i )
    {
        scanf("%d %d",&N,&M);
        for( j = 1 ; j <= M ; ++j )
        {
            scanf("%d %d",&x,&y);
            Mat[x][y] = Mat[y][x] = 1;
        }
        scanf("%d",&S);
        InitD();
        BFS();
        Tipar();
    }
    return 0;
}

Sursa a mers pe 4 din 7 teste. Am È™i testele pe care a luat WA, dar ele depÄƒÈ™esc limita de 50000 de caractere permise pe forum. :-'
MÄƒ poate ajuta cineva ?

infoarena

infoarena - concursuri, probleme, evaluator, articole => Probleme externe => Subiect creat de: FMI Razvan Birisan din Iulie 30, 2015, 09:16:33