多校4 lazy running (最短路)lazy running(最短路)

lazy running(最短路)

题意: 一个环上有四个点，从点2出发回到起点，走过的距离不小于K的最短距离是多少 (K <= 10^{18} 1 <= d <= 30000)

看完这道题，觉得这是个智力题，想了一想，无从下手啊
每次总是看完题解，就豁然开朗

其实之前做过一个类似的题，题目

但是根本想不到第一步, 选2w来转换啊，而且也不知道正确性啊

这类题要仔细理解一番

复制代码#include<bits/stdc++.h> #define LL long long #define P pair<int,int> using namespace std; const LL inf = 1e18; const int N = 6e4 + 10; int g[4][4]; int mod; LL K; LL dis[4][N]; int inq[4][N]; void spfa(){ for(int i = 0;i < 4;i++){ for(int j = 0;j < mod;j++) { dis[i][j] = inf,inq[i][j] = 0; } } queue<P> q; dis[1][0] = 0,inq[1][0] = 0; q.push(P(1,0)); while(!q.empty()){ P cur = q.front();q.pop(); for(int i = -1;i <= 2;i+=2){ int x = (cur.first + i + 4)%4, y = (cur.second + g[cur.first][x])%mod; if(dis[x][y] > dis[cur.first][cur.second] + g[cur.first][x]){ dis[x][y]= dis[cur.first][cur.second] + g[cur.first][x]; if(!inq[x][y]){ inq[x][y] = 1; q.push(P(x,y)); } } } } } int main() { int T; cin>>T; while(T--){ cin>>K; for(int i = 0;i < 4;i++) { scanf("%d",&g[i][(i+1)%4]); g[(i+1)%4][i] = g[i][(i+1)%4]; } mod = 2 * min(g[0][1],g[1][2]); spfa(); LL ans = 2e18; for(int i = 0;i < mod;i++){ LL d = K - dis[1][i]; ans = min(ans, dis[1][i] + (d + mod - 1) / mod * mod); } printf("%lldn",ans); } return 0; }

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
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
using namespace std;
const LL inf = 1e18;
const int N = 6e4 + 10;
int g[4][4];
int mod;
LL K;
LL dis[4][N];
int inq[4][N];
void spfa(){
for(int i = 0;i < 4;i++){
for(int j = 0;j < mod;j++) {
dis[i][j] = inf,inq[i][j] = 0;
}
}
queue<P> q;
dis[1][0] = 0,inq[1][0] = 0;
q.push(P(1,0));
while(!q.empty()){
P cur = q.front();q.pop();
for(int i = -1;i <= 2;i+=2){
int x = (cur.first + i + 4)%4, y = (cur.second + g[cur.first][x])%mod;
if(dis[x][y] > dis[cur.first][cur.second] + g[cur.first][x]){
dis[x][y]= dis[cur.first][cur.second] + g[cur.first][x];
if(!inq[x][y]){
inq[x][y] = 1;
q.push(P(x,y));
}
}
}
}
}
int main()
{
int T;
cin>>T;
while(T--){
cin>>K;
for(int i = 0;i < 4;i++) {
scanf("%d",&g[i][(i+1)%4]);
g[(i+1)%4][i] = g[i][(i+1)%4];
}
mod = 2 * min(g[0][1],g[1][2]);
spfa();
LL ans = 2e18;
for(int i = 0;i < mod;i++){
LL d = K - dis[1][i];
ans = min(ans, dis[1][i] + (d + mod - 1) / mod * mod);
}
printf("%lldn",ans);
}
return 0;
}