Lazy Running
There are 4 checkpoints in the campus, indexed as p1,p2,p3 and p4 . Every time you pass a checkpoint, you should swipe your card, then the distance between this checkpoint and the last checkpoint you passed will be added to your total distance.
The system regards these 4 checkpoints as a circle. When you are at checkpoint pi , you can just run to pi−1 or pi+1 ( p1 is also next to p4 ). You can run more distance between two adjacent checkpoints, but only the distance saved at the system will be counted.

Checkpoint p2 is the nearest to the dormitory, Little Q always starts and ends running at this checkpoint. Please write a program to help Little Q find the shortest path whose total distance is not less than K .
In each test case, there are 5 integers K,d1,2,d2,3,d3,4,d4,1(1≤K≤1018,1≤d≤30000) , denoting the required distance and the distance between every two adjacent checkpoints.
1 2000 600 650 535 380
2165HintThe best path is 2-1-4-3-2.
取w=min(d1,2,d2,3),那么对于每一种方案,均可以通过往返跑w这条边使得距离增加2w。也就是说,如果存在距离为k的方案,那么必然存在距离为k+2w的方案。
设disi,j表示从起点出发到达i,距离模2w为j时的最短路,那么根据dis2,j解不等式即可得到最优路线。
个人理解:首先,若是存在一种可行的方案,从2点出发,最后回到2点,这时的路径为xi,那么对于所有的xi,我们都可以通过往返与2相邻的最短路径w,使得xi+2*w,这时的xi+2*w路径也是一种可行方案,并且是相对于xi增量最少,同时我们还能发现,xi和xi+2*w都属于一个同余系,那么这个时候,问题来了,如果我们能找到一个同余系中最小的数,那么我们就能构造出这个同余系的所有数。有一点需要注意的是,这个同余系存在的意义是在某种方案可行的条件下,也就是说,最后的终点必须是2,如果我们能找到所有的可行方案,并且找到了可行方案同余系中的最小值,那么我们肯定可以从所有的同余系最小值中构造出满足题目要求也就是≥K的最小值。那么此时我们的目标就是从2点出发,最后回到2点的所有方案中,找出所有同余系的最小值,然后根据xi+n*2*w≥K的不等式,求出当前同余系能够构造的最小值,然后再求最小值。讲到这里,这个还是跟最短路没什么联系嘛~T_T。注意,这里的同余系最小值就是需要用最短路SPFA或者Dijkstra来求出的,用d[i][j]表示从2点出发,到达i点的,同余系为j的最小值,其中j=(2点到i点的距离) % (2*w)。跑完最短路之后,就是对j∈[0~2*w-1]的d[2][j]构造≥K的最小值,然后再求最小值,当然,当d[2][j]本身≥K的时候,直接比较就行了。(YY了两天,似乎YY出了能够说服自己的思路~QAQ)。
#include<bits/stdc++.h>
#define Max 1e18+9
using namespace std;
int T;
long long K;
struct Edge{
int v;
long long w;
};
vector<Edge> vec[5];
int m;
void add(int u,int v,int w){
Edge temp;
temp.v=v;
temp.w=w;
vec[u].push_back(temp);
}
void input(){
for(int i=1;i<=4;i++){
vec[i].clear();
}
int a,b,c,d;
scanf("%lld%d%d%d%d",&K,&a,&b,&c,&d);
m=min(a,b);
m*=2;
add(1,2,a),add(2,1,a);
add(2,3,b),add(3,2,b);
add(3,4,c),add(4,3,c);
add(4,1,d),add(1,4,d);
}
long long d[5][60005];
int id[5][60005];
void SPFA(){
for(int i=1;i<=4;i++){
for(int j=0;j<60005;j++){
d[i][j]=Max;
id[i][j]=0;
}
}
Edge temp;
id[2][0]=1;
d[2][0]=0;
temp.v=2;
temp.w=0;
queue<Edge> q;
q.push(temp);
while(q.empty()==0){
Edge t1=q.front();
q.pop();
int u=t1.v;
int w=t1.w;
id[u][w]--;
int len=vec[u].size();
//printf("len=%dn",len);
for(int i=0;i<len;i++){
int v=vec[u][i].v;
int w1=vec[u][i].w;
if(d[u][w]+w1<d[v][(d[u][w]+w1)%m]){
d[v][(d[u][w]+w1)%m]=d[u][w]+w1;
if(id[v][(d[u][w]+w1)%m]==0){
id[v][(d[u][w]+w1)%m]++;
Edge t2;
t2.v=v;
t2.w=(d[u][w]+w1)%m;
q.push(t2);
}
}
}
}
}
void solve(){
long long ans=Max;
for(int i=0;i<m;i++){
if(d[2][i]!=Max){
long long temp=K-d[2][i];
if(temp<=0){
ans=min(ans,d[2][i]);
}
else{
ans=min(ans,d[2][i]+(temp/m+(temp%m!=0?1:0))*m);
}
}
}
printf("%lldn",ans);
}
int main(){
scanf("%d",&T);
while(T--){
input();
SPFA();
solve();
}
return 0;
}
最后
以上就是专一小懒虫最近收集整理的关于HDU 6071 Lazy Running(同余最短路) Lazy Running的全部内容,更多相关HDU内容请搜索靠谱客的其他文章。
发表评论 取消回复