第一感觉是很离谱, 尤其是长度不限, 并且不会处理各个 $t$ 之间拼接之后包含的新的 $t$ .

这个长度 $3$ 很特点, 发现如果长度 $2$ 可以直接每个字母建一个点, 然后弄一下边权, 那么现在考虑直接建点 $(a, b)$ 表示当前字母是 $b$ , 上一个字母是 $a$ , 权值就又可以用点之间的边表示了.

注意起点终点和长度为 $1, 2$ 的字符串的细节.

赛时代码, 仅供参考.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;

const int M = 20000, N = 2000, C = 26, TM = C * C * C, TN = C * C;
int gh(char a, char b) {
    return a * C + b;
}
int gh(char a, char b, char c) {
    return a * C * C + b * C + c;
}

ll w[M], wn[N], sw[N], tw[N];
vector<pair<int, ll> > G[N];
ll dis[N];
int cnt[N];
bool instk[N];
int main() {
    int n;
    int res = -2e9;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        char s[4];
        int v;
        cin >> (s + 1) >> v;
        int l = strlen(s + 1);
        for (int i = 1; i <= l; i++)
            s[i] -= 'a';
        if (l == 1) {
            res = max(res, v);
            for (int i = 0; i < C; i++) {
                wn[gh(s[1], i)] += v;
                tw[gh(i, s[1])] += v;
            }
        } else if (l == 2) {
            wn[gh(s[1], s[2])] -= v;
            for (int i = 0; i < C; i++) {
                w[gh(i, s[1], s[2])] += v;
                w[gh(s[1], s[2], i)] += v;
            }
            sw[gh(s[1], s[2])] += v;
            tw[gh(s[1], s[2])] += v;
        } else {
            w[gh(s[1], s[2], s[3])] += v;
        }
    }

    for (int i = 0; i < TM; i++) {
        G[i / C + TN].push_back({i % (C * C), w[i]});
    }
    int s = TN * 2 + 1, t = s + 1;
    for (int i = 0; i < TN; i++) {
        G[i].push_back({i + TN, wn[i]});
        G[s].push_back({i, sw[i]});
        G[i + TN].push_back({t, tw[i]});
    }

    queue<int> q;
    memset(cnt, 0, sizeof(cnt));
    memset(dis, -0x3f, sizeof(dis));
    q.push(s);
    dis[s] = 0;
    instk[s] = true;
    while (q.size()) {
        int u = q.front();
        q.pop();
        cnt[u]++;
        instk[u] = false;
        if (cnt[u] > TN + 10) {
            cout << "Infinity" << endl;
            return 0;
        }
        for (pair<int, ll> e : G[u]) {
            ll v = e.first, w = e.second;
            if (dis[v] < dis[u] + w) {
                dis[v] = dis[u] + w;
                if (!instk[v]) {
                    instk[v] = true;
                    q.push(v);
                }
            }
        }
    }

    cout << max(1ll * res, dis[t]) << endl;
}