MICEMAZE  Mice and Maze
A set of laboratory mice is being trained to escape a maze. The maze is made up of cells, and each cell is connected to some other cells. However, there are obstacles in the passage between cells and therefore there is a time penalty to overcome the passage Also, some passages allow mice to go oneway, but not the other way round.
Suppose that all mice are now trained and, when placed in an arbitrary cell in the maze, take a path that leads them to the exit cell in minimum time.
We are going to conduct the following experiment: a mouse is placed in each cell of the maze and a countdown timer is started. When the timer stops we count the number of mice out of the maze.
Problem
Write a program that, given a description of the maze and the time limit, predicts the number of mice that will exit the maze. Assume that there are no bottlenecks is the maze, i.e. that all cells have room for an arbitrary number of mice.
Input
The maze cells are numbered $1, 2, \ldots, N$, where $N$ is the total number of cells. You can assume that $N \le 100$.
The first three input lines contain $N$, the number of cells in the maze, $E$, the number of the exit cell, and the starting value $T$ for the countdown timer (in some arbitrary time unit).
The fourth line contains the number $M$ of connections in the maze, and is followed by $M$ lines, each specifying a connection with three integer numbers: two cell numbers $a$ and $b$ (in the range $1, \ldots, N$) and the number of time units it takes to travel from $a$ to $b$.
Notice that each connection is oneway, i.e., the mice can't travel from $b$ to $a$ unless there is another line specifying that passage. Notice also that the time required to travel in each direction might be different.
Output
The output consists of a single line with the number of mice that reached the exit cell $E$ in at most $T$ time units.
Example
Input: 4 2 1 8 1 2 1 1 3 1 2 1 1 2 4 1 3 1 1 3 4 1 4 2 1 4 3 1 Output: 3
hide comments
chetan4060:
20171212 10:29:48
dijkstra's rocks:) 

thanhbinh84:
20171207 03:11:01
Don't be fool by ideal sample TC. >_<


vishesh197:
20171104 13:25:38
you can do it in two ways first is do bfs from all vertices to exit cell adding the time(cost) and checking if time is less


rohit1507:
20170904 01:30:53
One can use anything... BFS,Dijkstra's, DFS.... as suitable! Just think simple. 

amit88265:
20170810 13:38:56
easy yet good problem .teaches some basics about dijkstra and connectivity 

rohit9934:
20170614 17:52:13
Guys never give up on this problem,It's super easy. Just 5 min ago i thought of quitting but then AC.


praney_rai:
20170531 09:35:51
:D blunder mistake cost me 5 WA :/


ajeetk_973:
20170401 20:51:46
easy one with dijkstra's, AC in one go(_)


nilabja16180:
20170314 12:48:38
AC in ONE GO!


vladimira:
20170302 12:22:39
Didn't use dijkstra. Reversed connections and counted cells that can be reached starting from exit cell in time less then T. If I could reach cell in less time than already did earlier added cell to deque and changed time[cell]. Just bfs with a little additions. Last edit: 20170302 12:23:39 
Added by:  overwise 
Date:  20071004 
Time limit:  0.310s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  ACM ICPC  SWERC 2001 