01112 - Mice and Maze

#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;

struct Data{ int p, d; } arr[101][100];

bool operator<(const Data &a, const Data &b)
{
    return a.d>b.d;
}
int main()
{
    int cases;
    scanf("%d", &cases);

    for(int n, e, t, m; cases-- && scanf("%d%d%d%d", &n, &e, &t, &m);)
    {
        int len[101]={}, dist[101], ans=0;
        memset(dist, 127, sizeof(dist));
        priority_queue<Data> q;
        q.push({e, dist[e]=0});

        for(int i=0, a, b, c; i<m; i++)
            scanf("%d%d%d", &a, &b, &c), arr[b][len[b]++]={a, c};

        while(!q.empty())
        {
            Data a=q.top();
            q.pop();

            if(dist[a.p]==a.d)
                for(int i=0; i<len[a.p]; i++)
                {
                    Data b=arr[a.p][i];

                    if(dist[b.p]>a.d+b.d)
                        q.push({b.p, dist[b.p]=a.d+b.d});
                }
        }
        for(int i=1; i<=n; i++)
            ans+=dist[i]<=t;

        printf("%d\n", ans);
        if(cases) puts("");
    }
}