【题解】外星物种的遗传物质
题面：
外星物种的遗传物质
在离太阳系很遥远的一个星球上，有一些奇特的物种，名为OIer
他们的遗传物质叫AC，类似于人类的DNA
AC也是链状的，但AC有头尾之分
组成AC的单体有26种，分别名为WA,TLE,RE,MLE,CE,PE,OLE,UKE......
为了方便表示，这里将这26中单体用26个小写字母表示
现在OIer们正在研究AC：
如何用最少的花费将一串AC变成另一串AC
现在OIer们有以下技术：
01：对于一串AC，可从尾部逐个删除单体，不需要任何花费
10：对于任何一个位置的单体，可以经过一些变化变成想要的单体，花费为所有变化的
总花费，变化规则OIer已经研究透了
11：对于一串AC，可以从尾部逐个添加任意一个单体，当在这串AC尾部第k次添加单体
时花费为k*c 现在给出m个变化规则，每个变化规则x，y，z表示x单体可花费z变成y单体
并有t对AC，每对AC中有两串长度至少为1的AC：s1，s2
对于每对AC，要求将s2变成s1最小花费是多少
又由于OIer超级喜欢二进制，所以最小花费均用二进制数输出
分析：
很明显我们需要知道任意一个单体x变成任意一个单体y的最小花费
这个就用多源最短路Floyd来处理，把各个单体看做结点共26个结点，然后跑一遍Floyd
然后再按两个字符串的长度分类
接着枚举位置，这个位置之前用“替换”，这个位置之后用“先删除后添加”
这样就能遍历所有情况了
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
long long m,t,c,e[27][27],q[10005];
char s1[10005],s2[10005];
long long cost(int x) {
return (x*x+x)*c/2;//“先删除后添加”所需的花费，x是作用的单体数，返回的结果就是等差数列前x项和
}
int main() {
scanf("%lld %lld %lld",&m,&t,&c);
char x[2],y[2];
long long z;
for(int i=0; i<26; i++)
for(int j=0; j<26; j++)
e[i][j]=1e14;
for(int i=0; i<26; i++)
e[i][i]=0;//自己变自己不需要花费
for(int i=1; i<=m; i++) {
scanf("%s %s %lld",x,y,&z);
e[x[0]-'a'][y[0]-'a']=min(e[x[0]-'a'][y[0]-'a'],z);
}
for(int k=0; k<26; k++)
for(int i=0; i<26; i++)
for(int j=0; j<26; j++)
if(e[i][k]+e[k][j]<e[i][j])
e[i][j]=e[i][k]+e[k][j];
long long ans,l,ls,a[64],ia;
for(int i=1; i<=t; i++) {
scanf("%s %s",s1,s2);
l=min(strlen(s1),strlen(s2));
ls=strlen(s1);
if(ls>l) {
ans=cost(ls);
q[0]=e[s2[0]-'a'][s1[0]-'a'];
for(int j=1; j<l; j++) {
q[j]=q[j-1]+e[s2[j]-'a'][s1[j]-'a'];
ans=min(ans,q[j-1]+cost(ls-j));
}
ans=min(ans,q[l-1]+cost(ls-l));
} else {
ans=cost(l);
q[0]=e[s2[0]-'a'][s1[0]-'a'];
for(int j=1; j<l; j++) {
q[j]=q[j-1]+e[s2[j]-'a'][s1[j]-'a'];
ans=min(ans,q[j-1]+cost(l-j));
}
ans=min(ans,q[l-1]);
}
ia=0;
if(ans==0) putchar('0');
while(ans) {
a[ia++]=ans&1;
ans>>=1;
}
for(int j=ia-1; j>=0; j--)
putchar('0'+a[j]);
putchar('\n');
}
return 0;
}