Ta dando 30% de WA, sabe pq??

1148.cpp

#include <iostream>
#include <queue>
#include <vector>
#include <climits>
#include <cstring>

#define MAX_V 550
#define ii pair<int, int>

using namespace std;

struct Comparator {
    bool operator() (const ii &a, const ii &b) {
        return a.second > b.second;
    }
};

int N;
int distancias[MAX_V];
int grafo[MAX_V][MAX_V];

void djikstra(const int orig, const int dest) {
    for (int i = 1; i <= N; i++) {
        distancias[i] = INT_MAX;
    }

    priority_queue<ii, vector<ii>, Comparator> heap;

    distancias[orig] = 0;
    heap.push(ii(orig, 0));

    bool encontrou_dest = false;

    while (!heap.empty() && !encontrou_dest) {
        ii a = heap.top();
        heap.pop();

        int v = a.first;
        int peso = a.second;

        for (int u = 1; u <= N; u++) {
            if (grafo[v][u] < 0)
                continue;

            if (distancias[u] > distancias[v] + grafo[v][u]) {
                distancias[u] = distancias[v] + grafo[v][u];
                heap.push(ii(u, distancias[u]));

                if (u == dest) {
                    encontrou_dest = true;
                    break;
                }
            }
        }
    }
}

int main() {

    int e, x, y, h, k, o, d, m = 0;

    while ((cin >> N >> e) && N && e) {
        memset(grafo, -1, sizeof grafo);

        if (m++)
            cout << endl;

        while (e--) {
            cin >> x >> y >> h;
            grafo[x][y] = h;

            if (grafo[y][x] >= 0)
                grafo[x][y] = grafo[y][x] = 0;

        }

        cin >> k;

        while (k--) {
            cin >> o >> d;
            djikstra(o, d);

            if (distancias[d] != INT_MAX) {
                cout << distancias[d] << endl;
            } else {
                cout << "Nao e possivel entregar a carta" << endl;
            }
        }
    }
    return 0;
}