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
K meters.
There are
4
4 checkpoints in the campus, indexed as
p1,p2,p3
p1,p2,p3 and
p4
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
4 checkpoints as a circle. When you are at checkpoint
pi
pi, you can just run to
pi−1
pi−1 or
pi+1
pi+1(
p1
p1 is also next to
p4
p4). You can run more distance between two adjacent checkpoints, but only the distance saved at the system will be counted.
Checkpoint
p2
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
K.
Input
The first line of the input contains an integer
T(1≤T≤15)
T(1≤T≤15), denoting the number of test cases.
In each test case, there are
5
5 integers
K,d1,2,d2,3,d3,4,d4,1(1≤K≤1018,1≤d≤30000)
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.
Output
For each test case, print a single line containing an integer, denoting the minimum distance.
Sample Input
1
2000 600 650 535 380
Sample Output
2165
Hint
The best path is 2-1-4-3-2.
分析:比赛的时候没开这道题,但是其实以前做过类似的题,假如存在一个最优解x,那么x+2*d(2,3)一定也是一个解,那么重新构图,把一个点按起点到其距离对2*d(2,3)取模拆分成最多60000个点,然后再在这个图上跑最短路就可以了.
#include <bits/stdc++.h>
using namespace std;
const long long INF = 2000000000000000000ll;
typedef pair<int,long long> pii;
typedef long long ll;
int T;
ll K,x,w,ans,d[5][60005];
bool vis[5][60005];
pii q[4*60005];
vector<pii> G[5];
ll deal(ll x)
{
if(x >= K) return x;
ll temp = (K-x)/w;
if((K-x) % w) temp++;
return x + temp*w;
}
int main()
{
scanf("%d",&T);
while(T--)
{
ans = INF;
memset(d,0x3f,sizeof(d));
memset(vis,0,sizeof(vis));
for(int i = 1;i <= 4;i++) G[i].clear();
scanf("%lld",&K);
for(int i = 1;i <= 4;i++)
{
scanf("%lld",&x);
G[i].push_back(make_pair(i % 4 + 1,x));
G[i % 4 + 1].push_back(make_pair(i,x));
}
w = G[2][0].second*2;
d[2][0] = 0;
int s = 0,t = 0;
q[t++] = make_pair(2,0);
vis[2][0] = true;
while(s != t)
{
pii it = q[s++];
int u = it.first;ll mod = it.second;
for(pii temp : G[u])
{
int v = temp.first;ll val = temp.second;
if(d[v][(mod + val) % w] > d[u][mod] + val)
{
d[v][(mod + val) % w] = d[u][mod] + val;
if(!vis[v][(mod + val) % w])
{
vis[v][(mod + val) % w] = true;
q[t++] = make_pair(v,(mod + val) % w);
}
}
}
vis[u][mod] = false;
}
for(int i = 0;i < w;i++) ans = min(ans,deal(d[2][i]));
cout<<ans<<endl;
}
}
