A set of laboratory mice is being trained to escape a maze. The maze is made up of cells, and each cell isconnected to some other cells. However, there are obstacles in the passage betweencells and therefore there is a time penalty to overcome the passageAlso, 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 arbitrarycell in the maze, take a path that leads them to the exit cell in minimumtime.

We are going to conduct the following experiment: a mouse is placed in each cell ofthe 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. Assumethat there are no bottlenecks is the maze, i.e. that all cells haveroom for an arbitrary number of mice.

Input 

The maze cells are numbered 1,2,...,N, where N is the total numberof cells. You can assume that N ≤ 100.

The first three input lines contain N , the number of cells in themaze, 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 connectionwith three integer numbers: two cell numbers a and b(in the range 1,..,N) and the number of time unitsit takes to travel from a to b.

Notice that each connection is one-way, i.e., the mice can't travel from b to aunless there is another line specifying that passage.Notice also that the time requiredto 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 atmost T time units.

Sample Input 

14 2 181 2 11 3 12 1 12 4 13 1 13 4 14 2 14 3 1

Sample Output 

3

給迷宮兩點之間會有障礙物要清除(雙向)，接著在限定時間內到達終點的老鼠有幾隻？
假設每個點都會有一隻老鼠。

可以選擇使用 dijkstra 或者 spfa 都可以，對於終點反過來當最短路的起點即可。

#include <stdio.h>
#include <queue>
#include <string.h>
using namespace std;
struct edge {
    int to, v;
    edge(int a, int b):
        to(a), v(b) {}
};
int main() {
    int testcase;
    int n, m, st, time;
    int i, j , k, x, y, v;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d %d %d", &n, &st, &time, &m);
        vector<edge> g[105];
        while(m--) {
            scanf("%d %d %d", &x, &y, &v);
            g[y].push_back(edge(x, v));
        }
        int dist[105], inq[105] = {};
        memset(dist, 63, sizeof(dist));
        dist[st] = 0;
        queue<int> Q;
        Q.push(st);
        while(!Q.empty()) {
            int tn = Q.front();
            Q.pop(), inq[tn] = 0;
            for(vector<edge>::iterator it = g[tn].begin();
                it != g[tn].end(); it++) {
                if(dist[it->to] > dist[tn] + it->v) {
                    dist[it->to] = dist[tn] + it->v;
                    if(inq[it->to] == 0) {
                        inq[it->to] = 1;
                        Q.push(it->to);
                    }
                }
            }
        }
        int ret = 0;
        for(i = 0; i <= n; i++ )
            if(dist[i] <= time)
                ret++;
        printf("%d\n", ret);
        if(testcase)
            puts("");
    }
    return 0;
}