Camins P25900


Statement
 

pdf   zip

thehtml

Considereu un graf dirigit sense cicles, amb alguns vèrtexs especials. Podeu comptar el nombre de camins que comencen en un vèrtex especial i acaben en un altre vèrtex especial?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb el nombre de vèrtexs n i el nombre d’arcs m. Segueixen m parells x y indicant un arc des d’x fins a y, amb xy. Finalment, tenim el nombre e de vèrtexs especials, seguits d’aquests e vèrtexs en qualsevol ordre. Suposeu 2 ≤ n ≤ 104, 1 ≤ m ≤ 5n, 2 ≤ en, que els vèrtexs es numeren a partir de ‍0, i que no hi ha més d’un arc des d’un vèrtex fins a un altre.

Sortida

Per a cada cas, escriviu quants camins comencen en un vèrtex especial i acaben en un altre vèrtex especial. Com que el resultat pot ser molt gros, feu els càlculs mòdul MOD = 109 + 7.

Pista

Segons com sigui la vostra solució, tinguen cura si feu una resta mòdul MOD.

Public test cases
  • Input

    2
    1  0 1
    2  0 1
    
    3
    3  1 2  2 0  1 0
    3  2 0 1
    
    3
    2  0 1  0 2
    2  1 2
    

    Output

    1
    4
    0
    
  • Information
    Author
    Javier López-Contreras
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++