这个题比较有意思的是 他求最短路跟联通时间有关
其实他是借用了 Floyd运算原理的一道题
Floyd是不断的拿新的点做中转减小路径权值
然后我们读题会发现 为了方便 我提供的数据都是不降的
开业时间数列 和查询的时间都是不降的
所以我们可以想到 只需要在查询的时候 进行最短路运算
每次查询我们判断一下 之前运算的够不够用
如果够用 直接去判断
如果能联通就累加一下之前跑出来的S串内包含的LEN%ST串的数量
否则 累加一个-ST -指负的
如果不够 我们就从上一次运算到的点开始，到xiaoyudengyu查询的时间 之间开业的店 那进Floyd去跑一下.
因为开业时间是不降序列而且对于点 所以 我们可以直接用上次跑到的点开始跑到小于等于开业时间的点
因为下一个查询的开业时间不会小于上一个所以不会出现最短路用的点的时间大于查询时间的情况。
然后我们会发现 这题字符串len有点大 find 会tle 所以我们需要采用字符串哈希 或者kmp

#include<bits/stdc++.h>
using namespace std;
long long int n, m, t[500][500], sj[500], T, num, R, Q;
long long int mod1 = 1610612741;
string str;
long long int f[1000000], p[1000000];
long long int sc[100000];
void floy(int k) {
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            t[i][j] = min(t[i][k] + t[k][j], t[i][j]);
        }
    }
}
string s, s1;
int main() {
    cin >> n >> m >> T >> R >> Q;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            t[i][j] = 1e17;
        }
    }
    for (int i = 0; i < n; i++)
        t[i][i] = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> sj[i];
    }

    cin >> s;
    p[0] = 1;
    for (int i = 1; i <= s.length(); i++)
    {
        f[i] = (f[i - 1] * 131 + (s[i - 1] - 'a' + 1)) % mod1;
        p[i] = (p[i - 1] * 131) % mod1;
    }
    for (int i = 0; i < T; i++)
    {
        long long int f1 = 0;
        cin >> s1;
        for (int j = 1; j <= s1.length(); j++)
        {
            f1 = (f1 * 131 + (s1[j - 1] - 'a' + 1)) % mod1;
        }
        for (int j = s1.length(); j <= s.length(); j++)
        {
            int r1 = j, l1 = j - s1.length();
            int r2 = s1.length(), l2 = 0;
            long long int qz = ((f[r1] - f[l1] * p[r1 - l1]) % mod1 + mod1) % mod1;
            long long int qzq = (f1 % mod1 + mod1) % mod1;
            if (qz == qzq)
            {
                sc[i]++;
            }
        }
    }
    for (int i = 0; i < m; i++)
    {
        long long int qd, zd, qz;
        cin >> qd >> zd >> qz;
        t[qd][zd] = t[zd][qd] = min(qz, t[zd][qd]);
    }
    long long int up = 0;
    for (int i = 0; i < Q; i++)
    {
        long long int qd, zd, tz;
        cin >> qd >> zd >> tz;
        while (sj[up] <= tz && up < n) {
            floy(up);
            up++;
        }
        if (sj[qd] <= tz && sj[zd] <= tz)
        {
            if (t[qd][zd] == 1e17)num -= T;
            else
            {
                if (num > 0 && num + sc[t[qd][zd] % T] < 0)
                    return -1;
                num += sc[t[qd][zd] % T];

            }
        }
        else
        {
            num -= T;
        }
    }
    if (num > R)
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }
    cout << num;
}