HDU 6071 - Lazy Running | 2017 Multi-University Training Contest 4

/*
HDU 6071 - Lazy Running [ 建模,最短路 ]
|
2017 Multi-University Training Contest 4
题意：
四个点的环，给定相邻两点距离，问从2号点出发，2号点结束，距离大于k的最短距离
d(i,j) < 30000， k <= 1e18
分析：
设 r = min(d(1,2), d(2,3))
假设距离 k 可达，则 k+2*r 也可达（来回走的形式）
故求出所有 d[i][j] 满足 d[i][j]%2r == j 的最短距离
然后对于每一个d[2][j] 求出 d[2][j] + x*(2r) >= k 的第一个数
*/
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL INF = (LL)(1e18)+5;
struct qnode {
int v; LL c;
qnode(int v = 0, LL c = 0) : v(v), c(c) {}
bool operator < (const qnode & r) const {
return c > r.c;
}
};
struct Edge {
int v; LL c;
Edge(int v = 0, LL c = 0) : v(v), c(c) {}
};
vector<Edge> edge[5];
bool vis[5][60005];
LL dist[5][60005];
priority_queue<qnode> que;
void Dijkstra(int r)
{
while (!que.empty()) que.pop();
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= 4; i++)
for (int j = 0; j <= r; j++) dist[i][j] = INF;
dist[2][0] = r;
que.push(qnode(2, 0));
while (!que.empty())
{
auto tmp = que.top(); que.pop();
int u = tmp.v;
LL w = tmp.c;
if (vis[u][w%r]) continue;
vis[u][w%r] = 1;
for (const auto& e : edge[u])
{
LL c = w + e.c;
if (!vis[e.v][c%r] && dist[e.v][c%r] > c)
{
dist[e.v][c%r] = c;
que.push(qnode(e.v, c));
}
}
}
}
void addedge(int u, int v, LL w)
{
edge[u].push_back(Edge(v, w));
edge[v].push_back(Edge(u, w));
}
LL k, d[5], r;
int main()
{
int t; scanf("%d", &t);
while (t--)
{
for (int i = 1; i <= 4; i++) edge[i].clear();
scanf("%lld", &k);
for (int i = 1; i <= 4; i++) scanf("%lld", &d[i]);
r = 2*min(d[1], d[2]);
addedge(1, 2, d[1]); addedge(1, 4, d[4]);
addedge(2, 3, d[2]); addedge(3, 4, d[3]);
Dijkstra(r);
LL ans = k+r;
for (int i = 0; i < r; i++)
{
if (dist[2][i] == INF) continue;
if (dist[2][i] >= k)
{
ans = min(ans, dist[2][i]);
}
else
{
LL s = k-dist[2][i];
LL l = ((s-1)/r+1) * r + dist[2][i];
ans = min(ans, l);
}
}
printf("%lldn", ans);
}
}