foreach my $elA (@arA) {
    foreach my $elB (@arB) {
        if ($elA eq $elB) {
            push @{$all{$elA}}, $elB." - from Array B";
        }
    }
    foreach my $elC (@arC) {
        if ($elA eq $elC) {
            push @{$all{$elA}}, $elC ." - from Array C";
        }
    }
}

##</code><code>##

foreach my $elA (@arA) {
    map { ($elA eq $_) and push @{$all{$elA}}, "$_ - from Array B" } @arB;
    map { ($elA eq $_) and push @{$all{$elA}}, "$_ - from Array C" } @arC;
}

##</code><code>##

#!/usr/bin/perl -w

use strict;
use warnings;
use Data::Dumper;

my @arA = qw( lion tiger dog cat snake );
my @arB = qw( tiger dragon lion );
my @arC = qw( dog phoenix );

my %all;

# This is the list of arrays we want to compare against "arA",
# where the key is the label, and the value is the corresponding
# array reference.
my $p = {
    'from Array B' => \@arB,
    'from Array C' => \@arC,
};

foreach my $elA (@arA) {
    foreach my $lbl (keys %$p) {
        map { ($elA eq $_) and push @{$all{$elA}}, "$_ - $lbl" } @{$p->{$lbl}};
    }
}

print Dumper %all;
# Then do some other things with %all...