---

#include <iostream>
#include <chrono>
#include <climits>
using namespace std;

const int N = 6;
char vertex_names[N] = { 'A','B','C','D','E','F' };
const int A = 0, B = 1, C = 2, D = 3, E = 4, F = 5;
int G[N][N];
int dist[N];
bool visited[N];

void dikstra(int s) 
{
    for (int v = 0; v < N; v++)
    {
        dist[v] = INT_MAX;
        visited[v] = false;
    }
    dist[s] = 0;
    for (int step = 0; step < N;step++) 
    {
        int u = -1;
        int min_d = INT_MAX;

        for (int i = 0;i < N;i++)
        {
            if (!visited[i] && dist[i] < min_d) 
            {
                min_d = dist[i];
                u = i;
            }
        }
        if (u == -1)break;
        visited[u] = true;
        for (int v = 0;v < N;v++) 
        {
            int w = G[u][v];
            if (w > 0) 
            {
                if (dist[u] != INT_MAX && dist[u] + w < dist[v]) 
                {
                    dist[v] = dist[u] + w;
                }
            }
        }
    }
}
int main()
{
    setlocale(LC_ALL, "Russian");

    for (int i = 0;i < N;i++)
    {
        for (int j = 0;j < N;j++) 
        {
            G[i][j] = 0;
        }
    }

    G[A][B] = 4;
    G[A][C] = 2;
    G[B][D] = 10;
    G[B][C] = 5;
    G[C][E] = 3;
    G[E][D] = 4;
    G[E][F] = 5;
    G[D][F] = 11;

    int start_vertex = A;

    auto start_time = chrono::high_resolution_clock::now();

    dikstra(start_vertex);

    auto end_time = chrono::high_resolution_clock::now();

    auto duration = chrono::duration_cast<chrono::microseconds>(end_time - start_time);

    cout << "Кротчайшее расстояние до вершины" << vertex_names[start_vertex] << ":" << endl;

    for (int i = 0;i < N;i++) 
    {
        cout << "До вершины: " << vertex_names[i] << ":";
        if (dist[i] == INT_MAX) 
        {
            cout << "нет пути" << endl;
        }
        else 
        {
            cout << dist[i] << endl;
        }
    }
    cout << "--------------------" << endl;
    cout << "Время выполнения: " << duration.count() << "mc" << endl;
    cout << "--------------------" << endl;
}