#include <iostream>
#include <vector>
#include <limits>
#include <chrono>
#include <mpi.h>
 
using namespace std;
 
// Структура для представления взвешенного ребра в графе
struct Edge {
    int to;
    int weight;
    Edge(int t, int w) : to(t), weight(w) {}
};
 
// Функция для нахождения кратчайших путей от источника ко всем остальным вершинам
void dijkstra(const vector<vector<Edge>>& graph, int source, vector<int>& dist, int rank, int size) {
    int V = graph.size();
    dist.assign(V, numeric_limits<int>::max());
    dist[source] = 0;
 
    // Очередь приоритетов для хранения вершин и их расстояний
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, source});
 
    while (!pq.empty()) {
        int u = pq.top().second;
        int d = pq.top().first;
        pq.pop();
 
        if (d > dist[u]) continue;
 
        // Параллельное распределение работы
        for (int v = rank; v < V; v += size) {
            for (const Edge& e : graph[v]) {
                if (dist[v] + e.weight < dist[e.to]) {
                    dist[e.to] = dist[v] + e.weight;
                    // Отправка обновленного расстояния всем процессам
                    MPI_Allreduce(MPI_IN_PLACE, &dist[e.to], 1, MPI_INT, MPI_MIN, MPI_COMM_WORLD);
                }
            }
        }
    }
}
 
int main(int argc, char** argv) {
    MPI_Init(&argc, &argv);
 
    int rank, size;
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Comm_size(MPI_COMM_WORLD, &size);
 
    // Пример представления графа (список смежности)
    vector<vector<Edge>> graph = {
        {{1, 10}, {2, 5}},     // Вершина 0: (1, 10), (2, 5)
        {{3, 1}},              // Вершина 1: (3, 1)
        {{1, 3}, {3, 8}},      // Вершина 2: (1, 3), (3, 8)
        {{0, 2}}               // Вершина 3: (0, 2)
    };
 
    int source = 0;
    vector<int> dist(graph.size(), numeric_limits<int>::max());
 
    auto start = chrono::high_resolution_clock::now();
    dijkstra(graph, source, dist, rank, size);
    auto end = chrono::high_resolution_clock::now();
 
    // Вывод результатов только из процесса с рангом 0
    if (rank == 0) {
        chrono::duration<double> elapsed_seconds = end - start;
        cout << "Dijkstra's algorithm took " << elapsed_seconds.count() << " seconds" << endl;
        for (int i = 0; i < dist.size(); ++i) {
            cout << "Distance from source to vertex " << i << ": " << dist[i] << endl;
        }
    }
 
    MPI_Finalize();
 
    return 0;
}
 

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8bGltaXRzPgojaW5jbHVkZSA8Y2hyb25vPgojaW5jbHVkZSA8bXBpLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKLy8g0KHRgtGA0YPQutGC0YPRgNCwINC00LvRjyDQv9GA0LXQtNGB0YLQsNCy0LvQtdC90LjRjyDQstC30LLQtdGI0LXQvdC90L7Qs9C+INGA0LXQsdGA0LAg0LIg0LPRgNCw0YTQtQpzdHJ1Y3QgRWRnZSB7CiAgICBpbnQgdG87CiAgICBpbnQgd2VpZ2h0OwogICAgRWRnZShpbnQgdCwgaW50IHcpIDogdG8odCksIHdlaWdodCh3KSB7fQp9OwoKLy8g0KTRg9C90LrRhtC40Y8g0LTQu9GPINC90LDRhdC+0LbQtNC10L3QuNGPINC60YDQsNGC0YfQsNC50YjQuNGFINC/0YPRgtC10Lkg0L7RgiDQuNGB0YLQvtGH0L3QuNC60LAg0LrQviDQstGB0LXQvCDQvtGB0YLQsNC70YzQvdGL0Lwg0LLQtdGA0YjQuNC90LDQvAp2b2lkIGRpamtzdHJhKGNvbnN0IHZlY3Rvcjx2ZWN0b3I8RWRnZT4+JiBncmFwaCwgaW50IHNvdXJjZSwgdmVjdG9yPGludD4mIGRpc3QsIGludCByYW5rLCBpbnQgc2l6ZSkgewogICAgaW50IFYgPSBncmFwaC5zaXplKCk7CiAgICBkaXN0LmFzc2lnbihWLCBudW1lcmljX2xpbWl0czxpbnQ+OjptYXgoKSk7CiAgICBkaXN0W3NvdXJjZV0gPSAwOwoKICAgIC8vINCe0YfQtdGA0LXQtNGMINC/0YDQuNC+0YDQuNGC0LXRgtC+0LIg0LTQu9GPINGF0YDQsNC90LXQvdC40Y8g0LLQtdGA0YjQuNC9INC4INC40YUg0YDQsNGB0YHRgtC+0Y/QvdC40LkKICAgIHByaW9yaXR5X3F1ZXVlPHBhaXI8aW50LCBpbnQ+LCB2ZWN0b3I8cGFpcjxpbnQsIGludD4+LCBncmVhdGVyPHBhaXI8aW50LCBpbnQ+Pj4gcHE7CiAgICBwcS5wdXNoKHswLCBzb3VyY2V9KTsKCiAgICB3aGlsZSAoIXBxLmVtcHR5KCkpIHsKICAgICAgICBpbnQgdSA9IHBxLnRvcCgpLnNlY29uZDsKICAgICAgICBpbnQgZCA9IHBxLnRvcCgpLmZpcnN0OwogICAgICAgIHBxLnBvcCgpOwoKICAgICAgICBpZiAoZCA+IGRpc3RbdV0pIGNvbnRpbnVlOwoKICAgICAgICAvLyDQn9Cw0YDQsNC70LvQtdC70YzQvdC+0LUg0YDQsNGB0L/RgNC10LTQtdC70LXQvdC40LUg0YDQsNCx0L7RgtGLCiAgICAgICAgZm9yIChpbnQgdiA9IHJhbms7IHYgPCBWOyB2ICs9IHNpemUpIHsKICAgICAgICAgICAgZm9yIChjb25zdCBFZGdlJiBlIDogZ3JhcGhbdl0pIHsKICAgICAgICAgICAgICAgIGlmIChkaXN0W3ZdICsgZS53ZWlnaHQgPCBkaXN0W2UudG9dKSB7CiAgICAgICAgICAgICAgICAgICAgZGlzdFtlLnRvXSA9IGRpc3Rbdl0gKyBlLndlaWdodDsKICAgICAgICAgICAgICAgICAgICAvLyDQntGC0L/RgNCw0LLQutCwINC+0LHQvdC+0LLQu9C10L3QvdC+0LPQviDRgNCw0YHRgdGC0L7Rj9C90LjRjyDQstGB0LXQvCDQv9GA0L7RhtC10YHRgdCw0LwKICAgICAgICAgICAgICAgICAgICBNUElfQWxscmVkdWNlKE1QSV9JTl9QTEFDRSwgJmRpc3RbZS50b10sIDEsIE1QSV9JTlQsIE1QSV9NSU4sIE1QSV9DT01NX1dPUkxEKTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KfQoKaW50IG1haW4oaW50IGFyZ2MsIGNoYXIqKiBhcmd2KSB7CiAgICBNUElfSW5pdCgmYXJnYywgJmFyZ3YpOwoKICAgIGludCByYW5rLCBzaXplOwogICAgTVBJX0NvbW1fcmFuayhNUElfQ09NTV9XT1JMRCwgJnJhbmspOwogICAgTVBJX0NvbW1fc2l6ZShNUElfQ09NTV9XT1JMRCwgJnNpemUpOwoKICAgIC8vINCf0YDQuNC80LXRgCDQv9GA0LXQtNGB0YLQsNCy0LvQtdC90LjRjyDQs9GA0LDRhNCwICjRgdC/0LjRgdC+0Log0YHQvNC10LbQvdC+0YHRgtC4KQogICAgdmVjdG9yPHZlY3RvcjxFZGdlPj4gZ3JhcGggPSB7CiAgICAgICAge3sxLCAxMH0sIHsyLCA1fX0sICAgICAvLyDQktC10YDRiNC40L3QsCAwOiAoMSwgMTApLCAoMiwgNSkKICAgICAgICB7ezMsIDF9fSwgICAgICAgICAgICAgIC8vINCS0LXRgNGI0LjQvdCwIDE6ICgzLCAxKQogICAgICAgIHt7MSwgM30sIHszLCA4fX0sICAgICAgLy8g0JLQtdGA0YjQuNC90LAgMjogKDEsIDMpLCAoMywgOCkKICAgICAgICB7ezAsIDJ9fSAgICAgICAgICAgICAgIC8vINCS0LXRgNGI0LjQvdCwIDM6ICgwLCAyKQogICAgfTsKCiAgICBpbnQgc291cmNlID0gMDsKICAgIHZlY3RvcjxpbnQ+IGRpc3QoZ3JhcGguc2l6ZSgpLCBudW1lcmljX2xpbWl0czxpbnQ+OjptYXgoKSk7CgogICAgYXV0byBzdGFydCA9IGNocm9ubzo6aGlnaF9yZXNvbHV0aW9uX2Nsb2NrOjpub3coKTsKICAgIGRpamtzdHJhKGdyYXBoLCBzb3VyY2UsIGRpc3QsIHJhbmssIHNpemUpOwogICAgYXV0byBlbmQgPSBjaHJvbm86OmhpZ2hfcmVzb2x1dGlvbl9jbG9jazo6bm93KCk7CgogICAgLy8g0JLRi9Cy0L7QtCDRgNC10LfRg9C70YzRgtCw0YLQvtCyINGC0L7Qu9GM0LrQviDQuNC3INC/0YDQvtGG0LXRgdGB0LAg0YEg0YDQsNC90LPQvtC8IDAKICAgIGlmIChyYW5rID09IDApIHsKICAgICAgICBjaHJvbm86OmR1cmF0aW9uPGRvdWJsZT4gZWxhcHNlZF9zZWNvbmRzID0gZW5kIC0gc3RhcnQ7CiAgICAgICAgY291dCA8PCAiRGlqa3N0cmEncyBhbGdvcml0aG0gdG9vayAiIDw8IGVsYXBzZWRfc2Vjb25kcy5jb3VudCgpIDw8ICIgc2Vjb25kcyIgPDwgZW5kbDsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IGRpc3Quc2l6ZSgpOyArK2kpIHsKICAgICAgICAgICAgY291dCA8PCAiRGlzdGFuY2UgZnJvbSBzb3VyY2UgdG8gdmVydGV4ICIgPDwgaSA8PCAiOiAiIDw8IGRpc3RbaV0gPDwgZW5kbDsKICAgICAgICB9CiAgICB9CgogICAgTVBJX0ZpbmFsaXplKCk7CgogICAgcmV0dXJuIDA7Cn0K

cHVibGljIGNsYXNzIHExewogIH0=

public class q1{
  }