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.

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 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.

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
quang20193069: 2023-11-30 16:04:23

Dijkstra's algorithm for each N mice, and count the shortest path from each mice to exit node

Last edit: 2023-11-30 16:05:04
Jarek Czekalski: 2023-03-04 12:56:10

The constraints for T are not given, but it turned that they use values greater than 2^32, but less than 2^64.

Raman Shukla: 2022-01-01 18:47:13

The time taken can be negative too!!

jdmoyle: 2021-07-12 20:36:34

@los_viking82 Thanks to you ..For the first time i got AC in one go :D

kelmi: 2021-01-21 15:16:01

How is it possible that my solution got accepted twice even though it didn't run in less than a second ?

aceash: 2020-10-01 14:08:39

no need for floyd warshall , single source dijkstra plus reverse edges will do the job :)

utkarsh_bansal: 2020-08-03 16:47:29

guys test cases are very weak to check your solution. try for this one :
5
5
2
6
1 5 1
1 2 1
2 1 1
2 3 1
3 4 1
4 5 1

output should be 5

manish_thakur: 2020-04-01 20:28:58

Dijkastra practice problem for beginners like me!

black_shroud: 2020-03-24 08:02:03

just remember that E is the exit cell number(index) not number of exit cells.

los_viking82: 2020-03-19 20:47:07

@sapjv Dijkstra's algorithm is meant to solve the Single Source shortest path problem, which essentially means that
the source vertex is fixed and we want to find the shortest(minimum weight) path to all other vertices. Notice here that in this problem, the destination vertex is fixed (the exit cell) while the source vertex is different for each mouse. It would be computationally inefficient if we run a Dijkstra for n different source vertices. Hence a better approach would be to reverse the edges so that we can treat the destination vertex (as the source vertex) and see how many mice are able to reach their starting vertex within the given time limit. This can be done by reversing the edges and then applying Dijkstra treating the exit cell as the "source vertex".


Added by:overwise
Date:2007-10-04
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