#C240925A. 「CSP2023-J 普及组」旅游巴士

标签（Label）

• 最短路算法
• 动态规划
• 数学推理

网址（Website）

[CSP-J 2023] 旅游巴士 - 洛谷

题解（Solution）

$\qquad$如何处理时间差必须为 $k$ 的倍数呢？发现 $k$ 很小，尝试用 $dp[x][j]$ 表示第 $x$ 个点，时间对 $k$ 取余后为 $j$ ，很容易推得 $dp[y][(j+1)\%k] = dp[x][j]+1$ 。

$\qquad$如何处理客流量的限制呢？通过样例观察可得，如果从 $0$ 时刻出发走到当前点的时间 $w$ ，当前边的要求为 $v$ ，且 $w<v$ ，则要再等 $k\times a$ 的时间才能使此时的 $w>v$ ，为了满足时间最少，应有 $w+k\times a>v$ 且 $w+k\times(a-1)<v$ ，可以通过计算得到 $a$ ，从而算得 $w$ 。

$\qquad$由于要求最少时间，使用 $\verb!dijkstra!$ 算法跑最短路即可。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 20005;
const int K = 105;
bool ST;

vector<P> ft[N];
int n,m,k;

priority_queue<P> q;
int dis[N][K];//到达第x个点，时间对k取余后的最小时间 
void dijkstra(){
	memset(dis,0x3f,sizeof dis);
	q.emplace(0, 1);
	while(q.size()){
		int x = q.top().y, w = -q.top().x;q.pop();
		for(auto p:ft[x]){
			int y = p.x, v = p.y;
			int nw = (w>=v) ? w : ((v-w-1)/k+1)*k + w;
			int j = (nw+1)%k;
			if(nw+1 < dis[y][j]){
				dis[y][j] = nw+1;
				q.emplace(-dis[y][j],y);
			}
		}
	}cout<<(dis[n][0]==inf?-1:dis[n][0])<<'\n';
}

bool ED;
signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("bus.in","r",stdin);
	freopen("bus.out","w",stdout);
	cin>>n>>m>>k;int Tim = clock();
	For(i,1,m){
		int x,y,v;cin>>x>>y>>v;
		ft[x].emplace_back(y,v);
	}dijkstra();
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}