HDU 6071 Lazy Running（同余最短路的应用）

Lazy Running

思路

还是利用同余的思想，假设存在一条长度为$k$的路，那么也一定存在一条$k+base$的路$base=2\ast min(d1,d2)$。

$dis[i][j]=x$表示的是，从$2->i$点$x\equiv j(\mathrm{m}\mathrm{o}\mathrm{d}base)$的满足条件的最小的$x$，所以我们只要求出所有的$dis[2][i]$，再通过同余的性质去得到我们的最短路的花费，对于$dis[2][i]>k$我们取$min(ans,dis[2][i])$，否则的话，我们取$min(ans,dis[2][i]+(k-dis[2][i]+mid-1)/mod\ast mod)$，之后我们就可以得到我们的正确解了

代码

/*
Author : lifehappy
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define endl 'n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const double pi = acos(-1.0);
const double eps = 1e-7;
const int inf = 0x3f3f3f3f;
inline ll read() {
ll f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-')
f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
return f * x;
}
void print(ll x) {
if(x < 10) {
putchar(x + 48);
return ;
}
print(x / 10);
putchar(x % 10 + 48);
}
const int N = 6e4 + 10;
ll dis[5][N], k, d1, d2, d3, d4, mod;
vector< pair< int, ll > > G[5];
void Dijkstra() {
priority_queue< pair< ll, int >, vector< pair< ll, int > >, greater< pair< ll, int > > > q;
q.push(mp(0, 2));
memset(dis, 0x3f, sizeof dis);
dis[2][0] = 0;
while(q.size()) {
auto temp = q.top();
q.pop();
if(temp.first > dis[temp.second][temp.first % mod]) continue;
for(auto i : G[temp.second]) {
int to = i.first;
ll w = i.second + temp.first;
if(dis[to][w % mod] > w) {
dis[to][w % mod] = w;
q.push(mp(w, to));
}
}
}
}
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = read();
while(t--) {
k = read(), d1 = read(), d2 = read(), d3 = read(), d4 = read();
mod = min(d1, d2) * 2;
for(int i = 1; i <= 4; i++) G[i].clear();
G[1].pb(mp(2, d1)), G[1].pb(mp(4, d4));
G[2].pb(mp(3, d2)), G[2].pb(mp(1, d1));
G[3].pb(mp(2, d2)), G[3].pb(mp(4, d3));
G[4].pb(mp(3, d3)), G[4].pb(mp(1, d4));
Dijkstra();
ll ans = 0x3f3f3f3f3f3f3f3f;
for(int i = 0; i < mod; i++) {
if(k < dis[2][i]) ans = min(ans, dis[2][i]);
else {
ans = min(ans, dis[2][i] + (k - dis[2][i] + mod - 1) / mod * mod);
}
}
printf("%lldn", ans);
}
return 0;
}

最后

以上就是平常大米为你收集整理的HDU 6071 Lazy Running（同余最短路的应用）的全部内容，希望文章能够帮你解决HDU 6071 Lazy Running（同余最短路的应用）所遇到的程序开发问题。

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