10986 - Sending email

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define M 20005
#define MAXINT 2147483647
using namespace std;

int List[M][250],W[M][250],adjNo[M];
int DjKastra(int,int);

int main()
{
    int N,c,i,x,y,m,n,s,t,w,k,q;
    //freopen("in.txt","r",stdin);
    scanf("%d",&N);

    for(c=1;c<=N;c++)
    {
        scanf("%d%d%d%d",&n,&m,&s,&t);
        memset(adjNo,0,sizeof(adjNo));
       
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&x,&y,&w);
            List[x][adjNo[x]] = y;
            List[y][adjNo[y]] = x;

            W[x][adjNo[x]++] = w;
            W[y][adjNo[y]++] = w;
        }

        printf("Case #%d: ",c);

        if(x==y)
        {
            printf("0\n");
            continue;
        }
        n = DjKastra(s,t);

        if(n<0)
            printf("unreachable\n");
        else
            printf("%d\n",n);
    }
    return 0;
}

int DjKastra(int x,int y)
{
    priority_queue<pair<int,int> >Q;
    pair <int,int> tmp;
    int i, j,d[M],t,w;
    bool Visited[M],flag;
   
    memset(Visited,false,sizeof(Visited));
    for(i=0;i<M;i++)d[i]=MAXINT;
    d[x] = 0;
    Q.push(pair <int,int>(d[x],x));
   
    while(!Q.empty())
    {
        tmp = Q.top();Q.pop();
        i = tmp.second;
        Visited[i] = true;
        if(i==y)return d[y];

        for (j = 0; j<adjNo[i]; j++)
        {
            t = List[i][j];
            w = W[i][j];
            if(!Visited[t] && d[t] > d[i] + w)
            {
                d[t] = d[i] + w;
                Q.push(pair <int,int>(-d[t], t));
            }
        }
    }
    return -1;
}