UVa 1112 – Mice and Maze [solved]

Posted on February 12, 2020 by Mobarak Hosen Shakil — Leave a comment

/******************************************
          Mobarak Hosen Shakil
        ICE, Islamic University
     ID: mhiceiuk(all), 29698(LOJ)
   E-mail: mhiceiuk @ (Gmail/Yahoo/FB)
 Blog: https://iuconvergent.wordpress.com
*******************************************/

#include<bits/stdc++.h>
using namespace std;

#define IOS             ios_base::sync_with_stdio(0);cin.tie(0)
#define LL              long long int
#define ULL             unsigned LL
#define READ(File)      freopen(File, "r", stdin)
#define WRITE(File)     freopen(File, "w", stdout)
#define FOR(i, a, b)    for(int i=a; i<b; i++)
#define REP(i, a, b)    for(int i=a; i>=b; i--)
#define PII             pair<int, int>
#define pb              push_back
#define nl              '\n'

#define dbl             printf("I'm here baby\n")

const int inf = 1<<30;
const LL INF  = 1e18;
const int MOD = 1e9+7;
const int MAXN = 300005;

/*** Custom Sorting ***/
bool Compare(const PII &x, const PII &y)
{
    if(x.first == y.first)
    {
        return x.second>y.second;
    }
    return x.first<y.first;
}

/** 3D Direction --> x, y, z **/
int dx[] = {-1,  1, 0,  0,  0,  0};
int dy[] = { 0,  0, 1, -1,  0,  0};
int dz[] = { 0,  0, 0,  0,  1, -1};
///          N,  S, E,  W,  U,  D

int cost[105];
vector<PII> Edge[105];

void Reset(int n)
{
    FOR(i, 0, n+1)
    {
        cost[i] = inf;
        Edge[i].clear();
    }
}

void Dijkstra(int e, int c, int T)
{
    priority_queue<PII, vector<PII>, greater<PII> > pq;

    pq.push({c, e});

    cost[e] = c;

    while(!pq.empty())
    {
        PII u = pq.top(); pq.pop();
        int uu = u.second;
        int tu = u.first;

        if(cost[uu]>T) continue;

        FOR(i, 0, Edge[uu].size())
        {
            PII v = Edge[uu][i];
            int tv = v.second;
            int vv = v.first;
            if((tu+tv)<cost[vv])
            {
                cost[vv] = tu + tv;
                pq.push({cost[vv], vv});
            }
        }
    }
}

void Print(int n)
{
    FOR(i, 1, n+1)
    {
        printf("%d ", cost[i]);
    }
    printf("\n");


}

int main()
{
    ///WRITE("output.txt");
    int tc;
    scanf("%d", &tc);

    while(tc--)
    {
        int n, e, t, m;
        scanf("%d%d%d%d", &n, &e, &t, &m);

        Reset(n);

        FOR(i, 0, m)
        {
            int x, y, c;
            scanf("%d%d%d", &x, &y, &c);
            Edge[y].push_back({x, c});
        }

        Dijkstra(e, 0, t);
        int tot = 0;
       /// Print(n);
        FOR(i, 1, n+1)
        {
            if(cost[i]<=t) tot++;
        }
        printf("%d\n", tot);
        if(tc != 0) printf("\n");
    }
    return 0;
}