Uri 1148.cpp

#include <bits/stdc++.h>

#define MAX 500
#define INFINITO 1000000

using namespace std;

int dijkstra(int m[][MAX], int from, int to, int n)
{
    priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int, int>>> pq;
    vector<bool> visiteds (n, false);

    pq.push(make_pair(0, from));
    visiteds[from] = true;

    while (not pq.empty())
    {
        auto actual = pq.top();
        pq.pop();

        if (actual.second == to)
            return actual.first;

        for (int i = 0;i < n; ++i)
        {
            if (m[actual.second][i] != -1)
            {
                if (not visiteds[i])
                {
                    visiteds[i] = true;
                    int cost = m[actual.second][i] + actual.first;
                    pq.push(make_pair(cost, i));
                }
            }
        }
    }

    return -1;
}

int dijkstra2(int m[][MAX], int from, int to, int n)
{
    priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int, int>>> pq;
    vector<bool> visiteds (n, false);
    vector<int> dist (n, INFINITO);

    dist[from] = 0;
    pq.push(make_pair(dist[from], from));

    while (!pq.empty())
    {
        auto actual = pq.top();
        pq.pop();

        if (not visiteds[actual.second])
        {
            visiteds[actual.second] = true;

            for (int i = 0;i < n; ++i)
            {
                if (m[actual.second][i] != -1)
                {
                    if (dist[i] > actual.first + m[actual.second][i])
                    {
                        dist[i] = actual.first + m[actual.second][i];
                        pq.push(make_pair(actual.first + m[actual.second][i], i));
                    }
                }
            }
        }
    }

    return (dist[to] == INFINITO ? -1 : dist[to]);
}

int main()
{
    int N, E;

    while (cin >> N >> E, N || E)
    {
        int m[MAX][MAX];
        memset(m, -1, sizeof(m));

        for (int i = 0;i < E; ++i)
        {
            int from, to, w;
            cin >> from >> to >> w;
            m[from - 1][to - 1] = w;

            if (m[to - 1][from - 1] != -1)
            {
                m[from - 1][to - 1] = m[to - 1][from - 1] = 0;
            }
        }

        int k;
        cin >> k;
        while (k--)
        {
            int from, to;
            cin >> from >> to;
            int result = dijkstra2(m, from - 1, to - 1, N);

            if (result != -1)
                cout << result << endl;
            else
                cout << "Nao e possivel entregar a carta" << endl;
        }
        cout << endl;
    }

    return 0;
}