CSP-J 2023 旅游巴士 题解

题目描述

有向图，1是入口，n是出口。每条道路行走耗时1 单位时间。巴士会在0,k,2k,3k…时刻开，小 Z坐巴士进入入口的时刻必须是 k 的倍数。坐巴士离开出口时刻也必须是 k 的倍数。不能在任何点 / 道路停留：一旦从起点出发，就必须不停走路，不能原地等待。每条道路有开放时间ai：走上这条道路的时刻必须≥ai。求最早离开出口的时刻（k 的倍数），无解输出 - 1。

暴力的思路

如果我确定了小 Z 进入景区的出发时刻 S（S一定是 k 的倍数：0,k,2k,3k…），那之后他就不停走路，每走一条边时间+1。
对每一个合法出发时间S，跑一遍 BFS，算出从S时刻出发，能到达n号点的最小到达时间。
然后在所有结果里，选出最小的、且是 k 倍数的到达时间。

暴力代码

#include<bits/stdc++.h>usingnamespacestd;intn,m,k;vector<pair<int,int>>g[10005];boolvis[10005][10005];intdist[10005][10005];intxbfs(intstart){memset(dist,0x3f,sizeof(dist));queue<pair<int,int>>q;dist[1][start%k]=start;q.push({1,start%k});while(!q.empty()){intu=q.front().first;intt=q.front().second;q.pop();inttime=dist[u][t];for(inti=0;i<g[u].size();i++){intv=g[u][i].first;inta=g[u][i].second;intnextime=time+1;if(nextime<a)continue;intnt=nextime%k;if(dist[v][nt]>nextime){dist[v][nt]=nextime;q.push({v,nt});}}}returndist[n][0];}voidbfs(){queue<pair<int,int>>q;q.push({1,0});while(!q.empty()){intu=q.front().first;intt=q.front().second;q.pop();if(u==n&&t%k==0){cout<<t;return;}if(vis[u][t%k]){continue;}vis[u][t%k]=1;for(inti=0;i<g[u].size();i++){q.push({g[u][i].first,t+1});}}cout<<-1;}intmain(){cin>>n>>m>>k;boolflag=true;intmaxn=0;while(m--){intu,v,w;cin>>u>>v>>w;maxn=max(maxn,w);g[u].push_back({v,w});if(w!=0){flag=false;}}if(flag){bfs();return0;}else{intl=0,r=maxn+n+k;intans=0x3f3f3f3f;while(l<=r){intmid=(l+r)/2;if(xbfs(mid)!=0x3f3f3f3f){ans=xbfs(mid);l=mid+1;}else{r=mid-1;}}if(ans==0x3f3f3f3f)cout<<-1;elsecout<<ans;}return0;}

AC思路

由于这道题是从一个点出发到另一个点的最短路径，所以我们可以考虑一下求最短路径的经典算法：dijkstra算法（狄杰斯特拉算法）。
视频讲解

AC代码

#include<bits/stdc++.h>usingnamespacestd;intn,m,k,ans=1e9;vector<vector<pair<int,int>>>g;boolvis[10005][105];voiddijkstra(){priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;q.push({0,1});while(!q.empty()){pair<int,int>cur=q.top();q.pop();intt=cur.first;intu=cur.second;if(u==n&&t%k==0){ans=min(ans,t);}if(vis[u][t%k])continue;vis[u][t%k]=1;for(inti=0;i<g[u].size();i++){intv=g[u][i].first;intw=g[u][i].second;intnt=t+1;if(nt<=w){nt+=(w-nt+k)/k*k;}q.push({nt,v});}}}intmain(){cin>>n>>m>>k;g.resize(n+1);for(inti=1;i<=m;i++){intu,v,w;cin>>u>>v>>w;g[u].push_back({v,w});}dijkstra();if(ans==1e9)cout<<-1;elsecout<<ans;return0;}