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(wlog 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("%I64dn",ans);
}
}

最后

以上就是暴躁玉米为你收集整理的Lazy Running(dijkstra+取模)的全部内容，希望文章能够帮你解决Lazy Running(dijkstra+取模)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。