题意：给你n个字符串，每个字符串s[i]都有相应的花费代价cost[i]。问用这些已有的串拼出一个给定的T串的最小花费是多少。

思路：已知有n个模式串，再给出一个匹配串。很标准的一道AC自动机的题，花费最小的话也很容易想到用dp来做，dp[i]代表能拼出T[1~i]的最小花费,转移方程 dp[i]=min(dp[i],dp[i-len(s[i])]+cost[i])。但是不能直接用匹配串跑一个裸的AC自动机，这里需要用到trans指针优化，否则会卡在一组数据上。（好菜啊...学了两天的AC自动机终于把这题补掉了

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define pii pair<int,int>
#define pll pair<ll, ll>
#define pb push_back
#define X first
#define Y second
inline ll gcd(ll a, ll b) { while (b != 0) { ll c = a % b; a = b; b = c; }return a < 0 ? -a : a; }
inline ll lowbit(ll x) { return x & (-x); }
const double PI = 3.14159265358979323846;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
inline ll rd() {
    ll x = 0, f = 1; char ch = getchar();
    while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
    return x * f;
}
const double eps = 1e-6;
const int M = 5e5 + 10;
const int N = 5e5 + 10;
string s[N];
int n;
map<string, int>mp;
map<string, int>cnt;
//int cnt[N];
ll cc[N];
ll dp[N];
struct AC_M {
    struct Node {
        int next[26];
        int fail = 0;
        int exit = 0;
        int trans = 0;
        ll cost = 0;
    }trie[M];

    int root = 1;
    int tot = 1;

    void init() {
        for (int i = 1; i <= tot; i++) {
            memset(trie[i].next, 0, sizeof trie[i].next);
            trie[i].exit = 0;
            //trie[i].num = 0;
            trie[i].fail = 0;
        }
        tot = 1;
    }

    void insert(string s, ll cc) {
        int len = s.length();
        int p = root;
        for (int i = 0; i < len; i++) {
            int x = s[i] - 'a';
            if (trie[p].next[x] == 0)trie[p].next[x] = ++tot;
            p = trie[p].next[x];
        }
        trie[p].exit = len;
        //trie[p].num = 1;
        if (trie[p].cost == 0)trie[p].cost = cc;
        else trie[p].cost = min(trie[p].cost, cc);
    }

    void build() {
        for (int i = 1; i <= n; i++) {
            insert(s[i], cc[i]);
        }
        queue<int>q;
        for (int i = 0; i < 26; i++) {
            if (trie[root].next[i]) {
                trie[trie[root].next[i]].fail = root;
                trie[trie[root].next[i]].trans = root;
                q.push(trie[root].next[i]);
            }
            else {
                trie[root].next[i] = root;
            }
        }

        while (q.size()) {
            int x = q.front(); q.pop();
            for (int i = 0; i < 26; i++) {
                int y = trie[x].next[i];
                int fafail = trie[x].fail;
                if (y) {
                    trie[y].fail = trie[fafail].next[i];
                    q.push(y);
                    int q = trie[y].fail;
                    if (trie[q].exit == 0) {
                        trie[y].trans = trie[q].trans;
                    }
                    else {
                        trie[y].trans = q;
                    }
                }
                else {
                    trie[x].next[i] = trie[fafail].next[i];
                }
            }
        }
    }

    void query(string T) {
        int len = T.length();
        int p = root;
        int ans = 0;
        for (int i = 1; i <= len; i++) {
            int x = T[i - 1] - 'a';
            p = trie[p].next[x];
            for (int t = p; t; t = trie[t].trans) {
                if (trie[t].cost) {
                    //cnt[T.substr(i - trie[t].exit + 1, trie[t].exit)]++;
                    if (i - trie[t].exit < 0)continue;
                    dp[i] = min(dp[i], dp[i - trie[t].exit] + trie[t].cost);
                }
            }
        }
    }
}_AC;

int main() {
    n = rd();
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        cc[i] = rd();
        //mp[s[i]] = i;
    }
    _AC.init();
    _AC.build();
    string T; cin >> T;
    memset(dp, INF, sizeof dp);
    dp[0] = 0;
    _AC.query(T);
    //for (int i = 1; i <= n; i++) {
    //  cout << cnt[s[i]] << endl;
    //}
    if (dp[T.length()] == INF)cout << -1 << endl;
    else cout << dp[T.length()] << endl;
}