#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

// Par: (peso, vértice)
typedef pair<int, int> Par;

void dijkstra(const vector<vector<Par>>& grafo, int origem, int n) {
    // Vetor de distâncias, inicializado com infinito
    vector<int> dist(n, INT_MAX);
    // Fila de prioridade: menor distância primeiro (min-heap)
    priority_queue<Par, vector<Par>, greater<Par>> fila;

    dist[origem] = 0;
    fila.push({0, origem});

    while (!fila.empty()) {
        auto [distAtual, u] = fila.top();
        fila.pop();

        // Se já encontrou caminho melhor, ignora
        if (distAtual > dist[u]) continue;

        // Percorre vizinhos
        for (const auto& [peso, v] : grafo[u]) {
            if (dist[v] > dist[u] + peso) {
                dist[v] = dist[u] + peso;
                fila.push({dist[v], v});
            }
        }
    }

    // Exibe resultado
    cout << "Distâncias a partir do vértice " << origem << ":\n";
    for (int i = 0; i < n; ++i) {
        cout << "Vértice " << i << ": ";
        if (dist[i] == INT_MAX) cout << "Inacessível";
        else cout << dist[i];
        cout << endl;
    }
}

int main() {
    int n = 6; // Número de vértices (0 a 5)
    vector<vector<Par>> grafo(n);

    // Adiciona arestas: u -> v com peso
    grafo[0].push_back({4, 1});
    grafo[0].push_back({2, 2});
    grafo[1].push_back({1, 2});
    grafo[1].push_back({5, 3});
    grafo[2].push_back({8, 3});
    grafo[2].push_back({10, 4});
    grafo[3].push_back({2, 4});
    grafo[3].push_back({6, 5});
    grafo[4].push_back({3, 5});

    dijkstra(grafo, 0, n); // Origem no vértice 0
    return 0;
}