UVa:10986 Sending email

Dijkstra 알고리즘 모델링 문제.우선 대기열로 최적화하고 시간 복잡도는elgv이며 v^2의 알고리즘으로 시간을 초과합니다.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#define MAXN 20005
using namespace std;
typedef  pair<int ,int>  Pair;
struct Edge
{
    int to,cost;
    Edge(int a=0,int b=0):to(a),cost(b) {}
};
int main()
{
    int T,kase=0;
    scanf("%d",&T);
    while(T--)
    {
        int n,m,S,T;
        scanf("%d%d%d%d",&n,&m,&S,&T);
        vector<Edge> adjlist[MAXN];
        for(int i=0; i<m; ++i)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            adjlist[v].push_back(Edge(u,w));
            adjlist[u].push_back(Edge(v,w));
        }
        int d[MAXN];
        memset(d,0x7f,sizeof(d));
        int INF=d[0];
        d[S]=0;
        priority_queue<Pair,vector<Pair>,greater<Pair> > pq;
        pq.push(Pair(0,S));
        while(!pq.empty())
        {
            Pair tmp=pq.top();
            pq.pop();
            int v=tmp.second;
            if(d[v]<tmp.first) continue;
            for(int i=0;i<adjlist[v].size();++i)
            {
                Edge t=adjlist[v][i];
                if(d[t.to]>d[v]+t.cost)
                {
                    d[t.to]=d[v]+t.cost;
                    pq.push(Pair(d[t.to],t.to));
                }
            }
        }
         printf("Case #%d: ",++kase);
         if(d[T]!=INF) printf("%d
",d[T]);
         else puts("unreachable");
    }
    return 0;
}