第一次刷到HDU第一名，趁现在没人比我高，截图来一发！！！！
对于这道题，我只想说一个字
妙！！！！
题意：
给你四个点，(1,2),(2,3),(3,4),(4,1)之间都有一条无向路径，让你从 2 号点出发，最后回到2号点，同时使得走过的距离大于等于 k ，并且 最小。
k很大，最大达到 1e18 ，四条路的范围不大于 3e4 。
思路：
这道题真的是太妙了！！！
说一下我比赛前后的思路，这里我称 从 起点 2 回到 2的回路为 E 回路。
先说一下我比赛的思路：
一开始我的思路是这样的，首先不考虑单纯的往返，那么E回路就有7种情况。
那么我考虑复杂度的话最多的就是4点成环且只有4条边的情况，对于这条已有的E回路，我们可以在任意一条路径走来回走，使得路径长度增大。
那么我们就可以将问题转化成为 ( a_1 \times x + a_2 \times y + a_3 \times z + a_4 \times p \geq k ) 这样的不等式 4点4边成环需要特殊判断
四个系数为 [0,1e18] ，我们要求找到四个系数，使得不等式成立并且左边的值最小。
可以考虑用 二分 做。但是明显复杂度不够而且很难实现……
*正解 ： *
同余 bfs (以前被我叫作 数位bfs……)
首先对于一个已得的E回路，我们可以用任一一条E回路对它进行扩展。
因为这个图的E回路有无穷多个，我这里任取一条 为 a 。
假设已得E回路 p ，有E回路 a ， 那么必然存在一条拓展E回路 p + a。
同理，必然存在( p + n \times a ) 的拓展E回路。
那么对于 ( p + n \times a \geq k ) ，那么 我们只要找出最小的 满足条件 的 p 。而这里的条件就是 ( p \in \left[ 0 , a \right) )。
答案开始显然了起来
对于一个E回路 eu ，我么只要找到 最小的 p 使得 ( p + n \times eu \geq k ) 即可。
其中 ( p \in \left[ k % eu , eu\right) )
那么，eu 的范围将影响到我们整个算法的复杂度，所以我们应取 eu 为 最小，而最小的 E回路为
( \min \left( d_{2,1} , d_{2,3} \right) \times 2 )
有个需要注意的地方就是我们在取同余距离的时候要注意不能超过原本的 k ，这里只要限制一下就可以了。
AC Code
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
const int maxn = 6e4 + 10;
ll k, times;
int d[5], w, ans;
bool vis[4][maxn];
struct node {
int pos, val;
ll time;
node() {}
node(int p, int v, ll t) { pos = p, val = v, time = t; }
};
queue<node> que;
void bfs(int st)
{
fill(vis, false), vis[st][0] = true;
node cur;
int tmp, l, r;
que.push(node(st, 0, 0));
while (!que.empty()) {
cur = que.front();
que.pop();
if (cur.pos == st && cur.val >= k)
ans = min(ans, cur.val);
l = (cur.pos + 3) & 3, r = (cur.pos + 1) & 3;
if (!vis[l][(tmp = cur.val + d[l]) % w] && tmp / w + cur.time <= times) {
que.push(node(l, tmp % w, tmp / w + cur.time));
vis[l][tmp%w] = true;
}
if (!vis[r][(tmp = cur.val + d[cur.pos]) % w] && tmp / w + cur.time <= times) {
que.push(node(r, tmp % w, tmp / w + cur.time));
vis[r][tmp%w] = true;
}
}
}
int main()
{
int T;
scanf("%d", &T);
while (T--) {
scanf("%lld", &k);
each(i, 4) scanf("%d", d + i);
w = 2 * min(d[0], d[1]), times = k / w, k %= w, ans = inf;
bfs(1);
if (ans < inf)
printf("%lld\n", w * times + ans);
else
printf("%lld\n", (times + 1) * w);
}
return 0;
}