UVA 1112 - Mice and Maze(cpp file)

Problem Type :Dijkstra


#include<stdio.h>
#include<string.h>
#include<queue>
#include<vector>
#define MAX 101
#define  INF 52312424
using namespace std;
int vertex,edge,source,ext,dist[MAX],cost[MAX][MAX];
vector<int>mat[MAX];
struct node
{
    int x,c;
    node(int d, int f)
    {
        x=d;
        c=f;
    }
    bool operator<(const node &p)const
    {
        return c>p.c;
    }
};
void djkstra(int s)
{
    int ux,i,j,vx;
    priority_queue<node>Q;
    dist[s]=0;
    Q.push(node(s,dist[s]));
    while(!Q.empty())
    {
        node top = Q.top();
        int ux = top.x;
        Q.pop();
        for(i=0; i<mat[ux].size(); i++)
        {
            vx= mat[ux][i];
            if(dist[vx]>dist[ux]+cost[ux][vx])
            {
                dist[vx]=dist[ux]+cost[ux][vx];
                Q.push(node(vx,dist[vx]));
            }
        }
    }

}
int main()
{
    int test,i,j,cas=0,m,n,c;
    scanf("%d",&test);
    while(test--)
    {
        scanf("%d %d %d %d",&vertex,&ext,&source,&edge);
        for(i=1; i<=edge; i++)
        {
            scanf("%d %d %d",&n,&m,&c);
            mat[m].push_back(n);
            cost[m][n]=c;
        }
        for(i=1; i<=vertex; i++)
        {
            dist[i]=INF;
        }
        djkstra(ext);
        int cou=0;
        for(i=1; i<=vertex; i++)
        {
            if(dist[i]<=source)
                cou++;
        }
        printf("%d\n",cou);
        if (test)
        {
            puts("");
        }
        for(i=0; i<=MAX; i++)
        {
            mat[i].clear();
        }
        memset(cost,0,sizeof cost);
    }

}