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 one-way, 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 count-down timer is started. When the timer stops we count the number of mice out of the maze.


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.


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 count-down 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 one-way, 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.


The output consists of a single line with the number of mice that reached the exit cell $E$ in at most $T$ time units.


1 2 1
1 3 1
2 1 1
2 4 1
3 1 1
3 4 1
4 2 1
4 3 1


hide comments
scorpy1: 2019-08-16 18:35:53

Hint: reverse the edges is important!

masterchef2209: 2019-05-13 06:01:21

AC in 1 go :D

hint-floyd warshall

mr_pandey: 2019-01-22 15:05:13

@vaishcr7 the shortest path from 2 to 1 is having length 3 in your test case. Thus the answer must be 2.
Any of the shortest path algorithms are acceptable. One can solve it using bfs/dfs too :))

phoemur: 2018-12-02 21:20:23

SPOJ toolkit is a mess for this problem... Many wrong and even invalid testcases...

However, with N <= 100 its easy to realize that any shortest path algorithm should get AC.
(Dijkstra's, Bellman-Ford, Floyd-Warshall, ...)

Floyd-Warshall is O(n^3) and had 0.00s of runtime here.

vaishcr7: 2018-10-19 19:32:42

After many tries , I am still getting WA. I have used simple bfs on exit cell, reversing the edges and tried out all from spojtoolkit. I am using java b/w. I dont know what to expect for the below test case but spojtoolkit says 2. Question doesn't answer about overwriting edges between two vertices. Also I'm not sure which test case is giving me errors. This is the test case though:
2 1 5
2 1 3

I think the answer should be one as I have considered a unique edge in one direction between two vertices.

Last edit: 2018-10-19 19:33:15
sachinspoj: 2018-10-07 05:11:57

solved with bfs :)

gopikrishna_p: 2018-07-16 07:35:55

poor english

ajayc1007: 2018-06-22 20:39:23

Remember, at each cell, there is a mice !

ankit1cool: 2018-06-17 21:28:39

Just reverse the edges and apply dijkstra's

m2do: 2018-05-13 10:56:09

The mouse is kept in the E cell as well. Hence answer will always be > 1. Use Dijkstra and Floyd-Warshall <3

Added by:overwise
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ACM ICPC -- SWERC 2001