MATT - Matts Trip

Matt finds himself in a desert with $N$ ($2 \leq N \leq 10$) oases, each of which may have food, water, and/or a palm tree. If oasis $i$ has food, then $F_i=1$ - otherwise, $F_i=0$. Similarly, $W_i=1$ if and only if oasis $i$ has water, and $P_i=1$ if and only if it has a palm tree. These 3 values are completely independent of one another.


Some pairs of these oases are connected by desert paths, which each take 1 hour to traverse. There are $M$ ($0 \leq M \leq 45$) such paths, with path $i$ connecting distinct oases $A_i$ and $B_i$ in both directions ($1 \leq A_i,B_i \leq N$). No pair of oases is directly connected by more than one path, and it's not guaranteed that all oases are connected by some system of paths.


Matt starts at an oasis $S$, and wants to end up at a different oasis $E$ ($1 \leq S,E \leq N$).

Both of these oases are quite nice - it's guaranteed that $F_S=W_S=P_S=F_E=W_E=P_E=1$.

Since he's in a hurry to get out of the desert, he wants to travel there in at most $H$ ($1 \leq H \leq 10^9$) hours.

However, he can only survive for up to $MF$ hours at a time without food, and up to $MW$ hours at a time without water ($1 \leq MF,MW \leq 4$). For example, if $MF=1$ and $MW=2$, then every single oasis he visits along the way must have food (as he would otherwise spend more than 1 hour without it), and he cannot visit 2 or more oases without water in a row.


Since Matt is a computer scientist, before actually going anywhere, he's interested in the number of different paths he can take that will get him from oasis $S$ to oasis $E$ alive in at most $H$ hours.

Note that there may be no such paths.

Being a computer scientist, he of course only cares about this number modulo ($10^9+7$).


Line $1$: 7 integers, $N$, $M$, $H$, $S$, $E$, $MF$, and $MW$


Next $N$ lines: 3 integers, $F_i$, $W_i$, and $P_i$, for $i = 1..N$


Next $M$ lines: 2 integers, $A_i$ and $B_i$, for $i = 1..M$


1 integer, the number of different valid paths, modulo ($10^9+7$)

Example 1


3 3 3 1 2 1 4

1 1 1

1 1 1

0 1 0

1 2

2 3

1 3


The two possible paths, described in terms of oases visited, are $1 \rightarrow 2$ and $1 \rightarrow 2 \rightarrow 1 \rightarrow 2$. Matt can never go to oasis 3, as it doesn't contain food, which he can't survive without for more than 1 hour. The path $1 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 1 \rightarrow 2$ is not valid, as it would take 5 hours rather than at most 3.

Note that oasis 3 is the only oasis without a palm tree.

Example 2


5 5 3 3 2 3 2

1 0 0

1 1 1

1 1 1

0 0 1

0 1 0

1 2

1 3

1 4

3 4

4 2


The two possible paths are $3 \rightarrow 1 \rightarrow 2$ and $3 \rightarrow 4 \rightarrow 2$.

This time, oases 1 and 5 are lacking in palm trees.

hide comments
koushik s: 2018-06-14 09:12:56

if start and end are at the same oasis and not moving a single step is also considered as a valid path?

RE: Yes, that counts as a path which takes 0 time.

Last edit: 2018-12-02 10:47:21
Radosav227: 2015-04-07 19:11:13

Fun problem , but there is a problem with the compilation on the SPOJ server.
I have written my solution in c# and ran it on ideone with your test cases and it is working fine there, it is also working on all of my machines , and i'm not even close to any of the limits, yet when i run it on the SPOJ server it get a SIGABRT error. Any ideas on how i can fix this?

Red: 2015-04-07 14:42:07

I am trying to submit solution, and my program is working fine, but when i submit it outputs runtime error (SIGSEGV), i checked there's no overflow, not accessing any thing i did not put in memory. I tried to register on forum but it won't send mi activation mail that's why I'm posting this here. Can anyone tell me what should I do?

Dragan Markoviæ: 2015-04-06 02:28:55

Very nice problem! :)

Last edit: 2015-04-06 02:42:47
PetarV: 2015-04-01 10:59:50

Very nice problem! :)

Federico Lebrón: 2013-05-11 06:25:11

Are the following two paths the same for Matt?

{A -> B -> A -> B -> C, A -> B -> C}

(That is, does Matt want walks, or paths? Does he count only simple paths, or with cycles as well?)

RE: Same as in sample 1, those are different paths, and paths with cycles are valid.

RE: Thanks :) AC, thanks a lot for this problem! I enjoyed it.

RE: Great, no problem!

Last edit: 2013-05-13 12:38:05
Edelweiss: 2013-05-10 16:44:22

The Explanation of Example 1 should be "1->2", not "1->3". ^^

RE: Oops, thanks - it's been fixed.

Last edit: 2013-05-10 16:44:54
Federico Lebrón: 2013-05-10 16:44:22

What are the palm trees used for?

RE: They look pretty nice.

Last edit: 2013-05-10 01:39:54

Added by:SourSpinach
Time limit:8s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem