- 通行后到达时间为 $T'' = T' + 1$，余数为 $(r + 1) \bmod k$；
- 用 $T''$ 更新 $d[v][(r+1) \bmod k]$。
最终答案为 $\min_{0 \leq r < k} d[n][r]$。

有 $n$ 个景点、$m$ 条道路，巴士每 $k$ 分钟一班。每条道路有开放时间 $t_{\text{open}}$，仅当当前时间 $\geq t_{\text{open}}$ 时可通过，通行耗时 1 分钟。求从景点 $1$ 到景点 $n$ 的最早到达时间。
**思路**：
设 $d[i][r]$ 表示到达景点 $i$ 时，当前时间模 $k$ 余 $r$ 的最早绝对时间。初始状态 $d[1][0] = 0$。
对每条边 $(u, v, t_{\text{open}})$，若当前时间为 $T = d[u][r]$，则：
- 若 $T < t_{\text{open}}$，需等待至首个 $\geq t_{\text{open}}$ 的发车时刻：
等待后时间 $T' = \left\lceil \frac{t_{\text{open}} - T}{k} \right\rceil \cdot k + T$；

**等待时间的计算：**
当我们需要在一条道路前等待时，计算公式为：
\[
\text{等待周期数} = \left\lceil \frac{\text{开放时间} - \text{当前时间}}{k} \right\rceil
\]
在代码中，我们使用整数除法来实现向上取整：
\[
x = \frac{\text{na} - \text{nt} + k - 1}{k}
\]
**余数的计算：**
走过一条道路需要1分钟，所以新的余数为：
\[
\text{新余数} = (\text{当前余数} + 1) \mod k
\] AI转的一个latex版本的

粘不完

#include<bits/stdc++.h>

using namespace std;

int main(){

 freopen("bus.in","r",stdin);

 freopen("bus.out","w",stdout);

 int n,m,k;

 cin>>n>>m>>k;

 int u[20005],v[20005],a[20005];

 vector<int> g[10005];

 for(int i=0;i<m;i++){

 cin>>u[i]>>v[i]>>a[i];

 g[u[i]].push_back(i);

 }

 int d[10005][105];

 for(int i=1;i<=n;i++)for(int j=0;j<k;j++)d[i][j]=1000000000;

 d[1][0]=0;

 queue<pair<int,int>> q;

 q.push(make_pair(1,0));

 while(!q.empty

三年oi一场空，不开long long 见祖宗

byd这题过不了了是吧

卑鄙bus

#感谢教练#顶峰相见#沉淀三年#一场longlong毁了我的oi梦#中专开局又如何