2017多校第4场 HDU 6071 Lazy Running 同余最短路

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6071

题意：给你一个由四个节点组成的环，求从节点2出发，回到节点2的不小于k的最短路。

解法：见ICPCCAMP上面这个题：点击打开链接  有叉姐的强力回答。那个题和这个是一样的思路。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL inf = 1e16;
const int maxn=5;
int T,d1,d2,d3,d4,n,s;
LL k,m;
struct edge{
int v;
LL w;
};
vector<edge>g[maxn];
LL dp[4][70000];
void Dijstra(int s){
priority_queue<pair<LL,int>,vector<pair<LL,int> >, greater<pair<LL, int>> >q;
for(int i=0; i<4; i++)
for(int j=0; j<m; j++)
dp[i][j]=inf;
dp[s][0]=0;
q.push(make_pair(0,s));
while(!q.empty())
{
LL d=q.top().first;
int u=q.top().second;
q.pop();
if(d>dp[u][d%m]) continue;
for(int i=0; i<g[u].size(); i++){
int v=g[u][i].v;
LL dis = d+g[u][i].w;
if(dp[v][dis%m]>dis){
dp[v][dis%m]=dis;
q.push(make_pair(dis,v));
}
}
}
}
int main()
{
scanf("%d", &T);
while(T--)
{
n=4;
s=1;
for(int i=0; i<4; i++) g[i].clear();
scanf("%lld%d%d%d%d",&k,&d1,&d2,&d3,&d4);
g[0].push_back(edge{1,1LL*d1});
g[1].push_back(edge{0,1LL*d1});
g[1].push_back(edge{2,1LL*d2});
g[2].push_back(edge{1,1LL*d2});
g[2].push_back(edge{3,1LL*d3});
g[3].push_back(edge{2,1LL*d3});
g[3].push_back(edge{0,1LL*d4});
g[0].push_back(edge{3,1LL*d4});
m = min(1LL*d1, 1LL*d2) * 2;
Dijstra(s);
// puts("fuck");
LL ans = 1e19;
for(int i=0; i<m; i++){
LL temp = k-dp[1][i];
if(temp<=0) ans=min(ans,dp[1][i]);
else ans=min(ans,dp[1][i]+temp/m*m+(temp%m>0)*m);
}
printf("%lldn", ans);
}
return 0;
}

最后

以上就是辛勤鸵鸟最近收集整理的关于2017多校第4场 HDU 6071 Lazy Running 同余最短路的全部内容，更多相关2017多校第4场内容请搜索靠谱客的其他文章。