Dijkstra's

#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <sstream>
#include <string>
#include <chrono>


using namespace std;
using vvi = vector<vector<int>>;

const int INF = 1e9;
vector<int> dijkstra_with_vector(const vvi& graph, int start)
{
    int n = graph.size();
    vector<int> dist(n, INF);
    vector<bool> visited(n, 0);
    vector<int> q = { start };

    dist[start] = 0;

    for (int i = 0; i < n - 1; ++i)
    {
        int u = -1;
        for (int j = 0; j < n; ++j)
            if (!visited[j] && (u == -1 || dist[j] < dist[u]))
                u = j;

        visited[u] = 1;

        for (int j = 0; j < n; ++j)
            if (graph[u][j] != 0 && !visited[j] && dist[u] != INF)
                if (dist[u] + graph[u][j] < dist[j])
                    dist[j] = dist[u] + graph[u][j];
    }



    return dist;
}

vector<int> dijkstra_with_queue(const vvi& graph, int start)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    vector<int> dist(graph.size(), INF);
    vector<bool> visited(graph.size(), 0);

    q.push({ 0, start });
    dist[start] = 0;


    while (!q.empty())
    {
        int u = q.top().second;
        int dist_u = q.top().first;
        q.pop();

        if (dist_u > dist[u]) continue;

        for (int i = 0; i < graph[u].size(); ++i)
        {
            if (graph[u][i] != 0 &&  dist[i] > dist_u + graph[u][i])
            {
                dist[i] = dist_u + graph[u][i];
                q.push({ dist[i], i });
            }
        }
    }
    return dist;
}


vector<vector<int>> get_data(int n)
{
    vector<vector<int>> graph(n, vector<int>(n, 0));
    string line;

    for (int i = 0; i < n; ++i)
    {
        getline(cin, line);
        istringstream ss(line);
        string edge;

        while (ss >> edge)
        {
            size_t comma_pos = edge.find(',');
            int neighbor = stoi(edge.substr(0, comma_pos)) - 1;
            int weight = stoi(edge.substr(comma_pos + 1));
            graph[i][neighbor] = weight;
        }
    }

    return graph;
}

vvi get_data_from_file(const string& filename, int n)
{
    ifstream infile(filename);
    vector<vector<int>> graph(n, vector<int>(n, 0));

    string line;
    for (int i = 0; i < n; ++i)
    {
        if (!getline(infile, line)) {
            cerr << "Error: Not enough lines in the file." << endl;
            break;
        }

        istringstream ss(line);
        string edge;

        while (ss >> edge)
        {
            size_t comma_pos = edge.find(',');
            int neighbor = stoi(edge.substr(0, comma_pos)) - 1;
            int weight = stoi(edge.substr(comma_pos + 1));
            graph[i][neighbor] = weight;
        }
    }

    infile.close();
    return graph;
}

int main()
{
    setlocale(LC_ALL, "ru");

    int n;
    cin >> n;
    int s, k;
    cin >> s >> k;
    s--; k--;


    string fname = "graph.txt";
    vvi graph = get_data_from_file(fname, n);


    auto start = chrono::high_resolution_clock::now();
    vector<int> dist = dijkstra_with_vector(graph, s);
    auto end = chrono::high_resolution_clock::now();
    chrono::duration<double>  rez = end - start;
    cout << "Время работы обычного алгоритма Дейкстры: " << rez << "\nОтвет: " << dist[k] << '\n';

    start = chrono::high_resolution_clock::now();
    dist = dijkstra_with_queue(graph, s);
    end = chrono::high_resolution_clock::now();
    rez = end - start;
    cout << "Время алгоритма Дейкстры с использованием очереди с приоритетом: " << rez << "\nОтвет: " << dist[k] << '\n';

    return 0;
}