Lazy Running(dijkstra+取模)

点击打开链接

 

取w=\min(d_{1,2},d_{2,3})w=min(d​1,2​​,d​2,3​​)，那么对于每一种方案，均可以通过往返跑ww这条边使得距离增加2w2w。也就是说，如果存在距离为kk的方案，那么必然存在距离为k+2wk+2w的方案。

设dis_{i,j}dis​i,j​​表示从起点出发到达ii，距离模2w2w为jj时的最短路，那么根据dis_{2,j}dis​2,j​​解不等式即可得到最优路线。

时间复杂度O(w\log w)O(wlogw)。

用了一次dijstra算法，d[i][j]表示到达第i个点时的距离模上2m的最短距离，然后最后在针对每种情况做比较，求出最小值

 

#include<bits/stdc++.h> typedef long long ll; using namespace std; int d1,d2,d3,d4; struct edge { int y; ll len; //edge(int y1,ll len1):len(len1),y(y1){} }; vector<edge> g[6]; ll d[5][100000],k,m; typedef pair<ll ,int> p;//为了配合优先队列,first 距离,second 位置 void dij(int s) { priority_queue<p,vector<p>,greater<p> > q; for(int i=0;i<4;i++) for(int j=0;j<=m;j++) d[i][j]=2000000000000000000; q.push(p(0LL,s)); while(!q.empty()) { ll w=q.top().first; int j=q.top().second; q.pop(); if(w > d[j][w%m]) continue;//如果距离比最短路径大，则跳过 for(int k=0;k<g[j].size();k++) { int y=g[j][k].y; ll dist=w + g[j][k].len; if(d[y][dist%m] > dist) //更新的时候更新取模后对应的点 { d[y][dist%m]= dist; q.push(p(dist,y)); } } } } int main() { //freopen("in.txt","r",stdin); std::ios::sync_with_stdio(false); int t; cin>>t; while(t--) { cin>>k>>d1>>d2>>d3>>d4; memset(g,0,sizeof(g)); g[0].push_back(edge{1,d1}); g[1].push_back(edge{0,d1}); g[1].push_back(edge{2,d2}); g[2].push_back(edge{1,d2}); g[2].push_back(edge{3,d3}); g[3].push_back(edge{2,d3}); g[3].push_back(edge{0,d4}); g[0].push_back(edge{3,d4}); m=2*min(d1,d2); //选取与2相邻较小的那个，取余后更小，效率更高 dij(1); ll ans=2000000000000000000; int p; for(int i=0;i<m;i++) //枚举剩余系下所有的可能的最小花费 { ll temp=k - d[1][i]; if(temp<=0) ans=min(ans,d[1][i]); else ans=min(ans,d[1][i] + temp/m*m + (temp%m >0)*m); } printf("%I64d\n",ans); } }