文章來源：http://www.zghlxwxcb.cn/news/detail-765637.html
typedef pair<int,int> PII;
bool st[1100];
int h[11000000],ne[11000000],w[11000000],e[11000000],idx;
int dist[50][50];
class Solution {
public:
void add(int a,int b,int c)
{
e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;
}
void heap_dijkstra(int index,int start)
{
dist[index][start] = 0;
priority_queue<PII,vector<PII>,greater<PII>> heap;
heap.push({0,start});
while(!heap.empty())
{
auto t = heap.top();
heap.pop();
int k = t.second,dis = t.first;
if(st[k]) continue;
else st[k] = true;
for(int i = h[k];i != -1;i = ne[i])
{
int j = e[i];
if(dist[index][j] > dist[index][k] + w[i])
{
dist[index][j] = dist[index][k] + w[i];
heap.push({dist[index][j],j});
}
}
}
}
long long minimumCost(string source, string target, vector<char>& original, vector<char>& changed, vector<int>& cost)
{
int n = original.size();
memset(h,-1,sizeof(h));
for(int i = 0;i < n;i++)
{
int a = original[i] - 'a';
int b = changed[i] - 'a';
int c = cost[i];
add(a,b,c);
}
memset(dist,0x3f,sizeof(dist));
for(int i = 0;i < 26;i++)
{
memset(st,0,sizeof(st));
heap_dijkstra(i,i);//預(yù)處理出來 i字符 到任意字符的最短距離
}
long long res = 0;
int m = source.size();
for(int i = 0;i < m;i++)
{
int a = source[i] - 'a';
int b = target[i] - 'a';
if(dist[a][b] == 0x3f3f3f3f) return -1;
res += dist[a][b];
}
return res;
}
};?文章來源地址http://www.zghlxwxcb.cn/news/detail-765637.html
到了這里，關(guān)于力扣377周賽第三題(圖論題目)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
