赵老师OJ

问题3285--变幻字符

时间限制: 1 Sec 内存限制: 512 MB
提交: 0 解决: 0
[提交] [状态] [讨论版] [命题人:]

雨荨和云海都在纸上写了一个仅包含小写字母的字符串。现在安远老师给出了n个变幻字符的规则。每个规则有三个参数：ch1, ch2, w，表示把ch1变成ch2，需要w的代价。现在安远老师给雨荨的任务就是，将她和云海写的字符串用这n个规则进行任意多次的变幻，变成相同的字符串，并且变幻的代价最小。

第一行为一个字符串，代表雨荨写的字符串。第二行为一个字符串，代表云海写的字符串。第三行为一个整数n，代表规则总数。接下来n行，每行为两个字符ch1，ch2，以及一个整数w，都用一个空格隔开。

输出一行一个整数，代表变幻的最小代价，如果无法变幻，输出-1。

【样例1】
uayd
uxxd
3
a x 8
x y 13
d c 3

【样例2】
abc
ab
6
a b 4
a b 7
b a 8
c b 11
c a 3
a c 0

【样例1】
21

样例1说明：将第一串的a变成x,代价是8，将第二串的第二个x变成y，代价是13，这样两串字符全变成uxyd,总代价是21。

【样例2】
-1