弗洛伊德算法求多源最短路径

Question

Answer 1

#include<bits/stdc++.h>
using namespace std;
char a[1005],b[1005],e,f;
int n,d[27][27],s=0;
int main(){
cin>>a>>b;
cin>>n;
for(int i=0;i<n;i++){
cin>>e>>f;
d[e-'a'][f-'a']=d[f-'a'][e-'a']=1;
}
for(int k=0;k<27;k++){
for(int i=0;i<27;i++){
for(int j=0;j<27;j++){
if(d[i][k]!=0&&d[k][j]!=0&&i!=j){
if(d[i][j]==0) d[i][j]=d[i][k]+d[k][j];
else d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
}
}
}
for(int i=0;i<strlen(a);i++){
s+=d[a[i]-'a'][b[i]-'a'];
}
cout<<s;
return 0;
}