题目描述有向图1是入口n是出口。每条道路行走耗时1 单位时间。巴士会在0,k,2k,3k…时刻开小 Z坐巴士进入入口的时刻必须是 k 的倍数。坐巴士离开出口时刻也必须是 k 的倍数。不能在任何点 / 道路停留一旦从起点出发就必须不停走路不能原地等待。每条道路有开放时间ai走上这条道路的时刻必须≥ai。求最早离开出口的时刻k 的倍数无解输出 - 1。暴力的思路如果我确定了小 Z 进入景区的出发时刻 SS一定是 k 的倍数0,k,2k,3k…那之后他就不停走路每走一条边时间1。对每一个合法出发时间S跑一遍 BFS算出从S时刻出发能到达n号点的最小到达时间。然后在所有结果里选出最小的、且是 k 倍数的到达时间。暴力代码#includebits/stdc.husingnamespacestd;intn,m,k;vectorpairint,intg[10005];boolvis[10005][10005];intdist[10005][10005];intxbfs(intstart){memset(dist,0x3f,sizeof(dist));queuepairint,intq;dist[1][start%k]start;q.push({1,start%k});while(!q.empty()){intuq.front().first;inttq.front().second;q.pop();inttimedist[u][t];for(inti0;ig[u].size();i){intvg[u][i].first;intag[u][i].second;intnextimetime1;if(nextimea)continue;intntnextime%k;if(dist[v][nt]nextime){dist[v][nt]nextime;q.push({v,nt});}}}returndist[n][0];}voidbfs(){queuepairint,intq;q.push({1,0});while(!q.empty()){intuq.front().first;inttq.front().second;q.pop();if(unt%k0){coutt;return;}if(vis[u][t%k]){continue;}vis[u][t%k]1;for(inti0;ig[u].size();i){q.push({g[u][i].first,t1});}}cout-1;}intmain(){cinnmk;boolflagtrue;intmaxn0;while(m--){intu,v,w;cinuvw;maxnmax(maxn,w);g[u].push_back({v,w});if(w!0){flagfalse;}}if(flag){bfs();return0;}else{intl0,rmaxnnk;intans0x3f3f3f3f;while(lr){intmid(lr)/2;if(xbfs(mid)!0x3f3f3f3f){ansxbfs(mid);lmid1;}else{rmid-1;}}if(ans0x3f3f3f3f)cout-1;elsecoutans;}return0;}AC思路由于这道题是从一个点出发到另一个点的最短路径所以我们可以考虑一下求最短路径的经典算法dijkstra算法狄杰斯特拉算法。视频讲解AC代码#includebits/stdc.husingnamespacestd;intn,m,k,ans1e9;vectorvectorpairint,intg;boolvis[10005][105];voiddijkstra(){priority_queuepairint,int,vectorpairint,int,greaterpairint,intq;q.push({0,1});while(!q.empty()){pairint,intcurq.top();q.pop();inttcur.first;intucur.second;if(unt%k0){ansmin(ans,t);}if(vis[u][t%k])continue;vis[u][t%k]1;for(inti0;ig[u].size();i){intvg[u][i].first;intwg[u][i].second;intntt1;if(ntw){nt(w-ntk)/k*k;}q.push({nt,v});}}}intmain(){cinnmk;g.resize(n1);for(inti1;im;i){intu,v,w;cinuvw;g[u].push_back({v,w});}dijkstra();if(ans1e9)cout-1;elsecoutans;return0;}
