hdu6071（最短路）

hdu6071

题意

四个点连接形成一个环，给出相邻两个点的距离，求从点 (2) 出发再回到 (2) 的路程大于等于 (K) 的最小值。

分析

首先我们让 (w=min(d12, d23)) ，那么如果存在一个合法的路程 (k) 必然会存在路程 (k + 2 * w) 。
让 (d[x][v]) 表示从 (2) 出发到 (x) 点时 (v = d[x][v] % (2 * w)) 的最小值。跑一遍最短路计算出 (d) 数组。
枚举区间 ([0, 2*w-1]) ，答案一定可以在这里面取到（如果不足 (K) ，不断加上 (2 * w) 直到大于 (K)）。
如果 (ans) 为答案，(ans % (2*w))的余数一定在 ([0, 2*w-1]) 间，对于每种余数，我们都求到了得到这个余数的最小值。

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> P;
const ll INF = 1e18;
const int MAXN = 6e4 + 10;
vector<P> G[MAXN];
ll d[5][MAXN];
void dijkstra(ll w, int s) {
for(int i = 1; i <= 4; i++) {
fill(d[i], d[i] + w, INF);
}
priority_queue<P, vector<P>, greater<P> >q;
q.push(P(0, s));
d[s][0] = 0;
while(!q.empty()) {
P p = q.top(); q.pop();
int v = p.second;
if(p.first > d[v][p.first % w]) continue;
for(int i = 0; i < (int)G[v].size(); i++) {
P e = G[v][i];
ll dist = e.first + d[v][p.first % w];
if(dist < d[e.second][dist % w]) {
d[e.second][dist % w] = dist;
q.push(P(dist, e.second));
}
}
}
}
int main() {
int T;
cin >> T;
while(T--) {
memset(G, 0, sizeof G);
ll K, d1, d2, d3, d4;
cin >> K >> d1 >> d2 >> d3 >> d4;
G[1].push_back(P(d1, 2));
G[2].push_back(P(d1, 1));
G[2].push_back(P(d2, 3));
G[3].push_back(P(d2, 2));
G[3].push_back(P(d3, 4));
G[4].push_back(P(d3, 3));
G[4].push_back(P(d4, 1));
G[1].push_back(P(d4, 4));
ll w = 2 * min(d1, d2);
dijkstra(w, 2);
ll ans = INF;
for(ll i = 0; i < w; i++) {
if(d[2][i] >= K) {
ans = min(ans, d[2][i]);
} else {
ll nd = K - d[2][i];
ans = min(ans, d[2][i] + nd / w * w + (nd % w > 0) * w);
}
}
cout << ans << endl;
}
return 0;
}