Guia Pesao P62371

Per moure’s per París, un membre dels equips UPC (aka Pesao) es va oferir per guiar el grup des d’un punt d’origen s fins a un punt de destí t. Malgrat les ganes que hi posava, els camins que acabava escollint no eren mai els millors: el grup sempre s’acostava a t, però en cap moment s’agafava un carrer que hi anés òptimament.

Específicament, sigui d(p) la distància mínima des de cada punt p fins a t. Si en algun moment s’estava en el punt x, i hi havia un carrer de longitud ℓ que connectava x amb un altre punt y, es podia passar pel carrer només si es donaven les dues condicions següents:

• d(y) < d(x), i.e., la distància a t sempre disminuia estrictament.
• No hi havia cap camí de distància mínima per anar des d’x fins a t que passés pel carrer. En altres paraules, ℓ + d(y) > d(x).

De quantes maneres es podria haver fet una ruta que anés des d’s fins a t tot complint les condicions anteriors?

Entrada

L’entrada consisteix en diversos casos, només amb nombres enters. Cada cas comença amb el nombre de punts n, el nombre de carrers bidireccionals m, l’origen s i el destí t, amb s ≠ t. Segueixen m ternes amb la informació de cada carrer x y ℓ, amb x ≠ y i 1 ≤ ℓ ≤ 10⁴. Podeu suposar 2 ≤ n ≤ 5 · 10⁴ i 0 ≤ m ≤ 5n. Els punts es numeren entre 0 i n−1. Pot haver-hi més d’un carrer entre dos punts donats. També pot ser que no hi hagi cap camí entre s i t.

Sortida

Per a cada cas, escriviu el nombre de camins possibles mòdul 10⁸ + 7.