[CSP-J 2023] 旅游巴士 题解

题意：在一个有向图内，寻找出发时间和结束时间都为 k 的非负整数倍，且经过一条路的时间不早于这条路的边权 a[i] 的最小出发时间和结束时间。
特殊性质1：a[i] = 0，即不需考虑路上边权。
特殊性质2：u[i] <= v[i]，即除自己可以到达自己外，不会存在编号大于自己的节点可以到达自己的情况。
特殊性质3：k <= 1，即可以从任意时刻出发和到达。
注：可能存在自己到达自己的情况。

首先，当特殊性质1和特殊性质3结合，可以直接进行搜索。

输出 -1 可以得到 CCF 施舍的 5 分。
暴力搜索点 1 ~ 5，定义 vis[x][y] 为当前点为 x 时，到达该点时间 % k = y 是否到达过，复杂度 O(nk)。
对于点 6 ~ 7，相当于直接寻找最短路，复杂度 O(n)。

正解：
分析时间复杂度，显然只有 O(nk) 或 O(mk) 及以下才能过。
vis 定义同点 1 ~ 5。定义 dis[i][j] 表示在从点 1 出发到达点 i 时当前时间 % k = j 的最短距离。
考虑使用 BFS 或 DFS，调用参数为当前时间和当前点。
相比于普通最短路需要增加用优先队列维护，保证使当前时间最小的点处于最前。
对于开放时间，若当前时间大于等于开放时间直接无视，否则将出发时间推迟 k 的倍数次直到道路开放（即在当地等待了相同时间）。
更新 dis[nown][(nowt + 1) % k]，使其取最小值，若不需要更新，则这个状态将走过的路程已有更优解，跳过。
输出答案，若 vis[n][0] = 0，则没有对应路径，输出 -1，否则输出 dis[n][0]（当时间可以完全被整除时到达 n 的最短时间）。
AC：

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll n, m, k;
int dis[20009][109];
bool vis[20009][109]; // vis[i][j] 在 j 
bool cek[10009][10009];

struct node{
	ll nown;
	ll nowt;
	
	bool operator < (const node &n) const
	{
		return nowt > n.nowt;
	}
};
struct edge{
	ll t;
	ll time;
};

vector<edge> e[20009];

void solve()
{
	for(int i = 0; i < 20009; i++)
	{
		for(int j = 0; j < 109; j++)
		{
			dis[i][j] = INT_MAX;
		}
	}
	
	cin >> n >> m >> k;
	
	for(ll i = 0; i < m; i++)
	{
		ll u, v, a;
		
		cin >> u >> v >> a;
		
		if(cek[u][v])
		{
			continue;
		}
		e[u].push_back({v, a});
	}
	
	priority_queue<node> q;
	
	dis[1][0] = 0;
	q.push({1, 0});
	
	while(!q.empty())
	{
		node nown = q.top();
		q.pop();
		
		ll nowx = nown.nown, nowt = nown.nowt;
		// cout << "now: " << nowx << " nowt: " << nowt << endl;
		
		if(vis[nowx][nowt % k])
		{
			continue;
		}
		
		  
		vis[nowx][nowt % k] = 1;
		
		for(ll i = 0; i < (ll)e[nowx].size(); i++)
		{
			ll t = (nowt + 1) % k;
			ll nxtx = e[nowx][i].t;
			ll needt = e[nowx][i].time; 
			
			// cout << "from " << nowx << " to " << nxtx << " need at min " << needt << endl;
			
			if(nowt >= needt) // 已经开启 
			{
				// cout << 1 << endl;
			  	t = nowt;
			}
			else // 需要等待 
			{
				// cout << 2 << " nowt: ";
			  	t = ((needt - nowt + k - 1) / k) * k + nowt;
			  	// t = needt;
			  	// cout << t << endl;
			}
			
			if(dis[nxtx][(nowt + 1) % k] > t + 1) // 可以松弛 
			{
				// cout << "nextx: " << nxtx << " next_t: " << t + 1 << " maxneed " << needt << endl;
				q.push({nxtx, t + 1});
				dis[nxtx][(t + 1) % k] = t + 1;
			}
		}
	}
	
	if(!vis[n][0]) // 在 k 的倍数时间内不能到达 
	{
		cout << -1 << endl;
	}
	else
	{
		cout << dis[n][0] << endl;
	}
	
	return;
}

int main(){
	freopen("bus.in", "r", stdin);
    freopen("bus.out", "w", stdout);
	
	// ios::sync_with_stdio(0);
	// cin.tie(0);
	// cout.tie(0); 
	
	solve();

    fclose(stdin);
	fclose(stdout);
	return 0;
}