I have an unoriented graph with n vertices and m edges, 1 <= n, m <= 100000. All edges have 0 or 1 weights (two vertices are connected even if the corresponding edge has 0 weight). Vertices indexing starts with 1. I need to find length of the shortest path from vertex A to vertex B.

Input data example:

4 5 1 3
1 2 1
2 3 0
3 4 1
4 1 1
1 3 0

From the first line I get: n = 4, m = 5, A = 1, B = 3. Then I get the elements of the adjacency list. The first number in each line is from-vertex, the second - to-vertex, and the last is the weight of current edge. 0 or 1.

In the output I must receive the length of the shortest path or -1 if the path doesn't exist.

Here is my solution using Dijkstra's algorithm:

#include <iostream>
...

using std::cout;
using std::cin;
using std::endl;
using std::vector;
using std::pair;
using std::string;
using std::map;

size_t INF = 200000;

int main() {
    size_t nVert,
        mEdges,
        start,
        end;
    cin >> nVert >> mEdges >> start >> end;
    vector<vector<pair<size_t, size_t>>> ajList(mEdges);
    size_t edStart, edEnd, weight;
    for (size_t vert = 0; vert < mEdges; ++vert) {
        cin >> edStart >> edEnd >> weight;
        ajList.at(edStart - 1).push_back(pair<size_t, size_t>(edEnd, weight));
    }

    vector<size_t> minLen(nVert, INF), 
        pred(nVert);
    minLen[start - 1] = 0;
    vector<char> used(nVert);
    for (size_t vert = 0; vert < nVert; ++vert) {
        size_t currentVert = -1;
        for (size_t j = 0; j < nVert; ++j) {
            if (!used[j] && (currentVert == -1 || minLen[j] < minLen[currentVert]))
                currentVert = j;
        }
        if (minLen[currentVert] == INF)
            break;
        used[currentVert] = true;

        for (size_t j = 0; j < ajList[currentVert].size(); ++j) {
            int to = ajList[currentVert][j].first - 1,
                len = ajList[currentVert][j].second;
            if (minLen[currentVert] + len < minLen[to]) {
                minLen[to] = minLen[currentVert] + len;
                pred[to] = currentVert;
            }
        }
    }

    if (minLen[end - 1] == INF)
        cout << -1;
    else
        cout << minLen[end - 1];
    return 0;
}

I know that Dijkstra is the fastest algorithm for searching the shortest path from one vertex to all other vertices, but in my case it takes too long.

• How can I optimize this code to make it working faster (this is the main problem)?
• If you see some bugs in this snippet, please, let me know.