Shortest path algorithm in 0-1-unoriented graph I have an unoriented graph with n vertices and m edges, 1 &lt;= n, m &lt;= 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 &lt;iostream&gt;
...

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 &gt;&gt; nVert &gt;&gt; mEdges &gt;&gt; start &gt;&gt; end;
    vector&lt;vector&lt;pair&lt;size_t, size_t&gt;&gt;&gt; ajList(mEdges);
    size_t edStart, edEnd, weight;
    for (size_t vert = 0; vert &lt; mEdges; ++vert) {
        cin &gt;&gt; edStart &gt;&gt; edEnd &gt;&gt; weight;
        ajList.at(edStart - 1).push_back(pair&lt;size_t, size_t&gt;(edEnd, weight));
    }

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

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

    if (minLen[end - 1] == INF)
        cout &lt;&lt; -1;
    else
        cout &lt;&lt; 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.
You should extract reading the data and the Dijkstra to their own method. It helps debugging. You don't have enough information to make a meaningful heuristic for A* anyway.

When filling the adjacency matrix you do it as if it is directional while your post says it's not:

for (size_t vert = 0; vert &lt; mEdges; ++vert) {
    cin &gt;&gt; edStart &gt;&gt; edEnd &gt;&gt; weight;
    ajList.at(edStart - 1).push_back(pair&lt;size_t, size_t&gt;(edEnd, weight));
    ajList.at(edEnd - 1).push_back(pair&lt;size_t, size_t&gt;(edStart, weight));
}


I suggest you use a priority queue of some sort; it lets you remove the current node in \$O(\log n)\$ instead of \$O(n)\$ (the first inner for loop in your code).