这题其实比较套路。

首先容易想到拆点，$dis_{i,j}$ 记录走到 $i$ 花费了 $j$ 次修改对应的最近时间。

然后可以考虑在跑最短路的时候分类讨论：

• 如果时间开放着就直接走。
• 如果早了，那么可以等到开始再走或者花费一次修改直接走。
• 如果晚了，那么可以花费一次修改强行走。

这题的终测数据有卡 SPFA 的性质，所以还在用 SPFA 的同学被卡掉了分。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 50000;
const int MAXK = 50;
const int INF = 1'000'000'000'000'000'000;
int T;
int n, m, k;
struct Edge
{
    int v, s, t, w;
};
vector<Edge> e[MAXN + 5];
//<距离，点的编号，修改次数>，也可以开结构体然后重载运算符
priority_queue<pair<int, pair<int, int>>> pq;
// 到达 i 号点，修改 j 次的最短路
int dis[MAXN + 5][MAXK + 5];
bool vis[MAXN + 5][MAXK + 5];
void work()
{
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= k; j++)
        {
            dis[i][j] = INF;
            vis[i][j] = false;
        }
    dis[1][0] = 0;
    pq.push({-0, {1, 0}});
    while (!pq.empty())
    {
        int u = pq.top().second.first;
        int d = pq.top().second.second;
        pq.pop();
        if (vis[u][d])
            continue;
        vis[u][d] = true;
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i].v;
            int s = e[u][i].s;
            int t = e[u][i].t;
            int w = e[u][i].w;
            // 不修改，等或者直接走
            if (dis[u][d] <= t &&
                dis[v][d] > max(dis[u][d], s) + w)
            {
                dis[v][d] = max(dis[u][d], s) + w;
                pq.push({-dis[v][d], {v, d}});
            }
            // 修改，如果没到开始时间就修改开始时间
            // 如果超过了结束时间就修改结束时间，都是只改一次相当于没有时间限制
            if (d < k && dis[v][d + 1] > dis[u][d] + w)
            {
                dis[v][d + 1] = dis[u][d] + w;
                pq.push({-dis[v][d + 1], {v, d + 1}});
            }
        }
    }
    int ans = INF;
    for (int i = 0; i <= k; i++)
        ans = min(ans, dis[n][i]);
    if (ans == INF)
        cout << -1 << "\n";
    else
        cout << ans << "\n";
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    while (T--)
    {
        cin >> n >> m >> k;
        for (int i = 1; i <= n; i++)
            e[i].clear();
        for (int i = 1; i <= m; i++)
        {
            int u, v, s, t, w;
            cin >> u >> v >> s >> t >> w;
            e[u].push_back((Edge){v, s, t, w});
            e[v].push_back((Edge){u, s, t, w});
        }
        work();
    }

    return 0;
}