Lazy Running

In HDU, you have to run along the campus for 24 times, or you will fail in PE. According to the rule, you must keep your speed, and your running distance should not be less than  K  meters.

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 .

1
2000 600 650 535 380

2165


Hint

The best path is 2-1-4-3-2.

 

题目大意：

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

解题思路：

    又是一个可能出现无限向下走的题目。面对这种问题有一个比较常见的处理方法就是利用同余。

    题目要求的是回路，回路有这样一个性质，任意两个回路可以连接构成一个新的回路。于是任意一个回路就可以表示成x+n*y的形式，其中x和y是两个回路。现在再回到利用同余防止循环，如果我们固定y（代码中用的变量名为m），那么对于任意两个模y同余的x的效果是相同的，我们只需要保留最小的那个即可。

    显然时间复杂度和y正相关，那么我们就取满足题意的最小回路作为y，然后利用最短路算法找到所有起点为1的相互关于y不同余的环，更新答案即可。在最短路的过程中，对于每一个点也只需要保留关于y不同余的路径即可。

AC代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <string>
#include <map>
#include <set>
#include <list>
using namespace std;
#define INF 0x3f3f3f3f3f3f3f3f
#define LL long long
#define fi first
#define se second
#define mem(a,b) memset((a),(b),sizeof(a))
const int MAXN=4+3;
const int MAXM=60000+3;
struct Node
{
int p;
LL dis;
Node(int p, LL d):p(p), dis(d){}
};
LL K, G[MAXN][MAXN], m, ans;
bool vis[MAXN][MAXM];
LL dist[MAXN][MAXM];//从1开始到达i，模m等于j的最短路
void spfa(int s)
{
queue<Node> que;
mem(vis, 0);
mem(dist, 0x3f);
que.push(Node(1, 0));
dist[1][0]=0;
vis[1][0]=true;
while(!que.empty())
{
int u=que.front().p;
LL now_dis=que.front().dis;
vis[u][now_dis%m]=false;
que.pop();
for(int i=-1;i<2;i+=2)
{
int v=(u+i+4)%4;
LL next_dis=now_dis+G[u][v], next_m=next_dis%m;
if(v==s)//形成环，更行答案
{
if(next_dis<K)
ans=min(ans, next_dis+((K-next_dis-1)/m+1)*m);
else ans=min(ans, next_dis);
}
if(dist[v][next_m]>next_dis)
{
dist[v][next_m]=next_dis;
if(!vis[v][next_m])
{
que.push(Node(v, next_dis));
vis[v][next_m]=true;
}
}
}
}
}
int main()
{
int T_T;
scanf("%d", &T_T);
while(T_T--)
{
scanf("%lld", &K);
for(int i=0;i<4;++i)
{
scanf("%lld", &G[i][(i+1)%4]);
G[(i+1)%4][i]=G[i][(i+1)%4];
}
m=2*min(G[1][0], G[1][2]);//最小环
ans=((K-1)/m+1)*m;//只使用最短的回路
spfa(1);
printf("%lldn", ans);
}
return 0;
}

最后

以上就是无限小甜瓜为你收集整理的HDU 6071 Lazy Running（同余+最短路） Lazy Running的全部内容，希望文章能够帮你解决HDU 6071 Lazy Running（同余+最短路） Lazy Running所遇到的程序开发问题。

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