题目传送门

思路

如果不考虑开放时刻这个问题的情况下就是模板题

我们可以拆点，将 $u$ 这一种状态 拆成 $1 $~ $k - 1$不同时刻的状态（相当于增加一个维度）

在处理时间时判断景点有没有开放，如果景点开放了就可以直接标记
如果没有开放，那么我们可以选择晚一次车 / 进入起点的时间晚了，相当于整体的时间往后挪

$Dijkstra$ 最短路 (时间复杂度$O(nk \times log_2(m k)$)

具体细节看代码

AC Code

#pragma GCC optimize("Ofast", "inline", "-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
#include <cstdio>

using namespace std;
const int N = 10010, INF = 0x3f3f3f3f;

int n, m, c;
vector<pair<int, int>> G[N]; // 存图
struct Node
{
    int u, i, d; // u是图中节点编号，i是需要时间对c取模
    // d是从1号点走到u号点需要的时间，可以理解为最短路中的距离
    bool operator<(const Node &W) const
    {
        return d > W.d;
    }
};             // 队列中的节点
int d[N][110]; // d[i][j]表示从1号节点走到i号节点需要的时间
// （j用于分层，时间对c取模）
bool vis[N][110]; // dijkstra算法的标记数组

void dijkstra() // 最短路算法
{
    priority_queue<Node> q;      // 优先队列
    memset(d, 0x3f, sizeof d);   // 对d初始化
    q.push({1, 0, d[1][0] = 0}); // 在队列中加入第一个元素
    while (q.size())
    {
        int u = q.top().u, i = q.top().i; // 当前队头的编号u，取模后的时间i
        q.pop();
        if (vis[u][i])
            continue;
        vis[u][i] = 1;                        // 标记
        for (int k = 0; k < G[u].size(); k++) // 枚举u相连的若干节点
        {
            int v = G[u][k].first, w = G[u][k].second; // v是u相连节点的编号，w是开放时间
            int t = d[u][i], j = (i + 1) % c;          // 取出到u节点的时间和v节点的位置j
            if (t < w)                                 // 景区还没开放
                t += (w - t + c - 1) / c * c;
            // t += ceil((w - t) * 1.0 / c) * c
            // 将t加上c的非负整数倍，相当于进入起点的时间同时往后移
            if (d[v][j] > t + 1)                 // u在t单位时间能进去，v就能在t + 1单位时间进去
                q.push({v, j, d[v][j] = t + 1}); // 入队
        }
    }
}

int main()
{
    scanf("%d%d%d", &n, &m, &c);
    while (m--)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        G[u].push_back(make_pair(v, w)); // 建一条从u到v开放时间是w的边
    }

    dijkstra();

    if (d[n][0] == INF) // n点未更新，就是走不到n点，更改为-1
        d[n][0] = -1;
    printf("%d\n", d[n][0]);

    return 0;
}

本蒟蒻第三次写题解，请多多谅解，大佬发现有问题可以在评论区指出