cpp dijkstra algorithm which runs 0ms


  • 0
    H
    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];
    	}
    };
    

Log in to reply
 

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