だから僕らは がんばって挑戦だよね

APIO2023 赛博乐园

  • ~2.54K 字
  1. 1. 分析
  2. 2. 代码
  3. 3. 闲话

“并没有 不一样 为何感到悲伤” —— 《尘降》

分析

首先把图反着跑，这样总通行时间除以 22 就变成了后续时间都除以 22，当前总通过时间为 00 就变成了后续时间都为 00。

然后把一个点拆开成 K+2K+2 个，第 ii 个代表经过 ii 次除以二操作的点，最后一个代表经过清零操作的点，然后跑最短路。

注意一下 HH 不能多次经过和不能达到为 −1-1，这样就有 9797 分了。

发现除以二操作做 log⁡2105×10910−6\log_2 \frac{10^5\times10^9}{10^{-6}} 次就会变成可以忽略的值，所以 KK 和 7070 取小的那一个就行。

代码

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
const int N = 100005,C = 72,L = 70;
typedef pair<double,pair<int,int>> LDII;
vector<pair<int,int>> g[N];
double dis[N][C];//清零和超过 L 次除以 2 视为一致

double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr){
    for(int k=0;k<N;k++){
        g[k].clear();
        for(int j=0;j<=L;j++)
            dis[k][j] = 2e18;
    }
    for(int k=0;k<M;k++){
        g[x[k]].emplace_back(y[k],c[k]);
        g[y[k]].emplace_back(x[k],c[k]);
    }
    priority_queue<LDII,vector<LDII>,greater<LDII>> q;
    q.push({0,{H,0}});
    dis[H][0] = 0;
    while(!q.empty()){
        auto [u,k] = q.top().second;
        q.pop();
        for(auto[v,w]:g[u]){
            if(v==H)
                continue;
            if(k>=L){//视作清零操作
                if(dis[v][L]>dis[u][k]){
                    dis[v][L] = dis[u][k];
                    q.push({dis[v][L],{v,L}});
                }
                continue;
            }
            if(arr[v]==0){
                if(dis[v][L]>dis[u][k]+w*1.0/(1ll<<k)){
                    dis[v][L] = dis[u][k]+w*1.0/(1ll<<k);
                    q.push({dis[v][L],{v,L}});
                }
                continue;
            }
            if(arr[v]==2&&k<K){
                if(dis[v][k+1]>dis[u][k]+w*1.0/(1ll<<k)){
                    dis[v][k+1] = dis[u][k]+w*1.0/(1ll<<k);
                    q.push({dis[v][k+1],{v,k+1}});
                }
            }
            if(dis[v][k]>dis[u][k]+w*1.0/(1ll<<k)){
                dis[v][k] = dis[u][k]+w*1.0/(1ll<<k);
                q.push({dis[v][k],{v,k}});
            }
        }
    }
    double ans = 2e18;
    for(int k=0;k<=L;k++)
        ans = min(ans,dis[0][k]);
    if(ans>1e18)
        return -1;
    return ans;
}

闲话

考试的时候用的是 5050 过了，死过以内。

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可