35分觀察到有六七個(gè)點(diǎn)ai0我們選擇直接無視其他點(diǎn)假裝小z進(jìn)入景區(qū)時(shí)所有道路都能通行了那么問題就轉(zhuǎn)換成一個(gè)簡單的廣搜了用一個(gè)隊(duì)列一層一層的把景點(diǎn)壓入當(dāng)?shù)搅私K點(diǎn)時(shí)就是最省時(shí)間的了。#includebits/stdc.husingnamespacestd;intn,m,k;vectorpairint,intg[10005];boolvis[10005][10005];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;return;}intmain(){cinnmk;while(m--){intu,v,w;cinuvw;g[u].push_back({v,w});}bfs();return0;}正解單源最短路可以用dijkstra來做。(這里給大家一個(gè)學(xué)迪杰斯特拉的網(wǎng)址我老師推薦的https://www.bilibili.com/video/BV1uT4y1p7Jy/?spm_id_from333.337.search-card.all.clickvd_sourceb59c08196148ea3ea8a331da551bf5a8總而言之dijkstra可以在中間添加路開通的時(shí)間判斷能否走下一步找最短時(shí)間。#includebits/stdc.husingnamespacestd;intn,m,k,ans1e9;vectorvectorpairint,intg;boolvis[10005][105];voiddijkstra(){priority_queuepairint,int,vectorpairint,int,greaterpairint,intq;//建立小根堆維護(hù)最短路徑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;}