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
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#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; }
转载于:https://www.cnblogs.com/ftae/p/7291768.html
最后
以上就是复杂烤鸡最近收集整理的关于hdu6071(最短路)的全部内容,更多相关hdu6071(最短路)内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复