HDU6071 Lazy Running 同余最短路

题意

一张图上有4个点，一开始在点2处 ，最终也回到点2处 ，问我们怎样走，使得总路径和大于等于K并且最小。输出最短路径值。

思路

同余思想：
令$w=min(di{s}_{12},di{s}_{23})$，取$min$是为了降低时空复杂度，代码里会看到。
w存在的意义就是可以一直在点2和点1或3之间无止境往返。
假设存在一条合法路径2->2，该路径长度为$len$，则$len+n\ast 2w$也是一条合法路径。而我们要找的就是最短路径。这些个路径会被$\%2w$分成$2w$组，求出每一组同余类$i$的合法路径长度，最后$ans$取$min$。

Dijkstra的过程中：
$dis[i][j]表示2到i的路径中\%w为j的最小值，所以要求出所有的dis[2][i]。$

更新答案：
$若dis[2][i]>=k，则ans=min(ans,dis[2][i])$
$若dis[2][i]<k，则ans=min(ans,dis[2][i]+若干2w)$

Code(62MS)

#include "bits/stdc++.h"
using namespace std;
typedef unsigned long long ll;
const int N = 1e6 + 10;
struct edge {
int v; ll w;
};
struct node {
int now; ll d;
bool operator < (const node& rhs) const {
return d > rhs.d;
}
};
vector<edge> g[5];
ll dis[5][N], w;
void Dij() {
for(int i = 1;i <= 4; i++) {
for(int j = 0;j < w; j++) {
dis[i][j] = 1e18;
}
}
dis[2][0] = 0;
priority_queue<node> q;
q.push({2, 0});
while(!q.empty()) {
node p = q.top(); q.pop();
int u = p.now;
if(dis[u][p.d % w] < p.d) continue;
for(auto e : g[u]) {
int v = e.v;
ll len = e.w + p.d;
if(dis[v][len % w] > len) {
dis[v][len % w] = len;
q.push({v, len});
}
}
}
}
void solve() {
int _; cin >> _;
while(_--) {
ll d12, d23, d34, d41, K;
cin >> K >> d12 >> d23 >> d34 >> d41;
g[1].emplace_back(edge{2, d12});g[2].emplace_back(edge{1, d12});
g[2].emplace_back(edge{3, d23});g[3].emplace_back(edge{2, d23});
g[3].emplace_back(edge{4, d34});g[4].emplace_back(edge{3, d34});
g[4].emplace_back(edge{1, d41});g[1].emplace_back(edge{4, d41});
w = 2 * min(d12, d23);
Dij();
ll ans = 1e19;
for(int i = 0;i < w; i++) {
if(dis[2][i] >= K) ans = min(dis[2][i], ans);
else ans = min(ans, dis[2][i] + (K - dis[2][i] + w - 1) / w * w);
}
cout << ans << endl;
for(int i = 1;i <= 4; i++) g[i].clear();
}
}
signed main() {
solve();
}

最后

以上就是沉静啤酒为你收集整理的HDU6071 Lazy Running 同余最短路的全部内容，希望文章能够帮你解决HDU6071 Lazy Running 同余最短路所遇到的程序开发问题。

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