wust 1599弗洛伊德

简单总结。。比赛一塌糊涂。。策略失误太严重。。要好好补补题。。

这题看上去就是构造弗洛伊德，然后枚举间接点。。

两个坑导致当时做不出来。。

1.memset 0x3f3f3f3f还是有毒啊。。。蒟蒻还是好好循环初始化吧。。

2.多写了一个ans[26][26],how[26][26]导致迷之问题。。很简单的问题为什么一定要搞得那么复杂呢。。太脑残

3.题意没注意忘记wi可以等于0啊。。最后才看见。。

反思，图论写的太少了。。水题都写不对。。代码能简单就往简单了写。。一点点复杂度解决不了问题。。

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cmath>
#include <vector>
#include <set>
#include <cstring>
#include <queue>

using namespace std;
const int maxn=100005;
string s1,s2;
long long gra[26][26];
long long ans[26][26];
long long how[26][26];
int n;
char rets[maxn];
long long inf=0x3f3f3f3f;
void f(){
    for(int k=0;k<26;k++){
        for(int i=0;i<26;i++){
            for(int j=0;j<26;j++){
                if(gra[i][k]!=inf&&gra[k][j]!=inf)
                gra[i][j]=min(gra[i][j],gra[i][k]+gra[k][j]);
            }
        }
    }
}

int main()
{
    int T;
    cin>>T;
    while(T--){
        cin>>s1>>s2;
        int n;
        int ns=s1.size();
        int ns2=s2.size();
        scanf("%d",&n);
        char a,b;
        long long c;
         for(int i=0;i<26;i++){
            for(int j=0;j<26;j++){
                gra[i][j]=inf;
            }
        }
        memset(rets,0,sizeof(rets));
        for(int i=0;i<n;i++){
            cin>>a>>b>>c;
            gra[a-'a'][b-'a']=min(c,gra[a-'a'][b-'a']);
        }
        if(ns!=ns2){
            cout<<"-1
";
            continue;
        }
        for(int i=0;i<26;i++)
            gra[i][i]=0;
        f();
        long long ret=0;
        long long add=0;
        int bo=1;
        for(int i=0;i<ns;i++){
            add=inf;
            for(int k=0;k<26;k++){
                if(gra[s1[i]-'a'][k]!=inf&&gra[s2[i]-'a'][k]!=inf){
                    if(add>gra[s1[i]-'a'][k]+gra[s2[i]-'a'][k]){
                        add=gra[s1[i]-'a'][k]+gra[s2[i]-'a'][k];
                        rets[i]=k+'a';
                    }
                }
            }
            if(add==inf){
                bo=0;
                break;
            }
            ret+=add;
        }
        if(bo==1){
            cout<<ret<<endl<<(string)rets<<endl;
        }
        else{
            cout<<"-1
";
        }
    }
    return 0;
}