# cpp dijkstra algorithm which runs 0ms

• ``````class Solution {
public:
int minMutation(string start, string end, vector<string>& bank) {
int n = bank.size();
if (n == 0)
return -1;
n++;
bank.push_back(start);
queue<int> q;
int target = -1;
vector<int> distance(n, 0);
vector<vector<int> > graphic(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) {
bool isEnd = true;
for (int j = 0; j < n; j++) {
int different = 0;
for (int k = 0; k < 8; k++) {
if (bank[i][k] != bank[j][k])
different++;
}
if (different == 1) {
graphic[i][j] = graphic[j][i] = 1;
distance[j] = 1;
}
}
for (int k = 0; k < 8; k++) {
if (bank[i][k] != end[k])
isEnd = false;
}
if (isEnd)
target = i;
}
if (target == -1)
return -1;
for (int i = 0; i < n - 1; i++) {
distance[i] = 2147483647;
q.push(i);
}
distance[n - 1] = 0;
q.push(n - 1);
while (!q.empty()) {
int oper = q.front();
q.pop();
queue<int> qt;
while (!q.empty()) {
int t = q.front();
q.pop();
if (distance[t] < distance[oper]) {
qt.push(oper);
oper = t;
}
else
qt.push(t);
}
while (!qt.empty()) {
q.push(qt.front());
qt.pop();
}
for (int i = 0; i < n; i++) {
if (graphic[oper][i] != 0) {
if (distance[oper] + 1 < distance[i])
distance[i] = distance[oper] + 1;
}
}
}
if (distance[target] == 2147483647)
return -1;
else
return distance[target];
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.