<p>A gene string can be represented by an 8-character long string, with choices from <code>&#39;A&#39;</code>, <code>&#39;C&#39;</code>, <code>&#39;G&#39;</code>, and <code>&#39;T&#39;</code>.</p>

<p>Suppose we need to investigate a mutation from a gene string <code>startGene</code> to a gene string <code>endGene</code> where one mutation is defined as one single character changed in the gene string.</p>

<ul>
	<li>For example, <code>&quot;AACCGGTT&quot; --&gt; &quot;AACCGGTA&quot;</code> is one mutation.</li>
</ul>

<p>There is also a gene bank <code>bank</code> that records all the valid gene mutations. A gene must be in <code>bank</code> to make it a valid gene string.</p>

<p>Given the two gene strings <code>startGene</code> and <code>endGene</code> and the gene bank <code>bank</code>, return <em>the minimum number of mutations needed to mutate from </em><code>startGene</code><em> to </em><code>endGene</code>. If there is no such a mutation, return <code>-1</code>.</p>

<p>Note that the starting point is assumed to be valid, so it might not be included in the bank.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> startGene = &quot;AACCGGTT&quot;, endGene = &quot;AACCGGTA&quot;, bank = [&quot;AACCGGTA&quot;]
<strong>Output:</strong> 1
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> startGene = &quot;AACCGGTT&quot;, endGene = &quot;AAACGGTA&quot;, bank = [&quot;AACCGGTA&quot;,&quot;AACCGCTA&quot;,&quot;AAACGGTA&quot;]
<strong>Output:</strong> 2
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= bank.length &lt;= 10</code></li>
	<li><code>startGene.length == endGene.length == bank[i].length == 8</code></li>
	<li><code>startGene</code>, <code>endGene</code>, and <code>bank[i]</code> consist of only the characters <code>[&#39;A&#39;, &#39;C&#39;, &#39;G&#39;, &#39;T&#39;]</code>.</li>
</ul>

class Solution {
public:
    unordered_map<string,vector<pair<string,int>>> adj;
    unordered_map<string,int> dist;
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        if(find(bank.begin(),bank.end(),startGene)==bank.end()) bank.push_back(startGene);
        int n = bank.size();
        for(int i=0;i<n;i++){
            dist[bank[i]]=1e9;
            for(int j=i+1;j<n;j++){
                int diff = 0;
                for(int k=0;k<8;k++) diff+=(bank[i][k]!=bank[j][k]);
                if(diff>1) continue;
                adj[bank[i]].push_back({bank[j],diff});
                adj[bank[j]].push_back({bank[i],diff});
            }
        }
        for(auto &[a,v]:adj){
            cout<<a<<": ";
            for(auto &[x,c]:v) cout<<"("<<x<<","<<c<<") ";
            cout<<endl;
        }
        priority_queue<pair<int,string>,vector<pair<int,string>>,greater<pair<int,string>>> pq;
        pq.push({0,startGene});
        dist[startGene] = 0;
        while(!pq.empty()){
            auto [d,curr] = pq.top(); pq.pop();
            for(auto [neigh,cost]:adj[curr]){
                if(dist[neigh]>d+cost){
                    dist[neigh] = d+cost;
                    pq.push({dist[neigh],neigh});
                }
            }
        }
        return (dist.find(endGene)==dist.end() or dist[endGene]==1e9 ? -1 : dist[endGene]);
    }
};
8600