Submission #1230507

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230507		hashdfdfh	Toll (BOI17_toll)	C++20	100 / 100	715 ms	79176 KiB

toll

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 5e4 + 5;
const int MAX_K = 5;

int k, n, m, q;

// 最大级别数，数值/k相同的放在一个层级
int level;

// 第一个维度：起始点所在级别
// 第二个维度：起始级别节点编号（%k结果）
// 第三个维度：目标级别节点编号（%k结果）
// 第四个维度：目标点所在级别（第一个维度 + 2^ 第四个维度 - 1）
int dat[MAX_N][MAX_K][MAX_K][16];

void build() {
    // 最多有n/k层
    n = n / k;
    level = log2(n);

    // 初始化表格
    // 计算每个长度是2^j的区间
    for (int j = 1; j <= level; j++) {
        for (int i = 0; i + (1 << j) <= n; i++) {
            // 需要求的级别区间：[i, i + 2 ^ j - 1]
            // 左侧区间：开始是i，长度是2^(j-1) [i, i + 2 ^ (j - 1) - 1]
            // 右侧区间：开始是i + 2 ^ (j - 1)，长度是2^(j-1) [i + 2 ^ (j - 1), i + 2 ^ j - 1]
            
            // 枚举左侧级别的每个节点编号
            for (int u = 0; u < k; u++) {
                // 枚举右侧级别的每个节点编号
                for (int v = 0; v < k; v++) {
                    // 枚举中间级别的每个节点编号，作为中继点
                    for (int p = 0; p < k; p++) {
                        // 第i个级别的第u个节点，到第i + 2 ^ j - 1个级别的第p个节点
                        // 第i + 2 ^ j个级别的第p个节点，到第i + 2 ^ j - 1个级别的第v个节点
                        int tmp = dat[i][u][p][j - 1] + dat[i + (1 << (j - 1))][p][v][j - 1];
                        dat[i][u][v][j] = min(dat[i][u][v][j], tmp);
                    }
                }
            }
        }
    }
}

void query(int a, int b) {
    // a所在层级
    int alevel = a / k;
    // b所在层级
    int blevel = b / k;
    // a所在层级节点编号
    int ano = a % k;
    // b所在层级节点编号
    int bno = b % k;

    // 计算两个层级的差距
    int dif = blevel - alevel;

    // 第一个维度：0表示前一轮结果，1表示当前轮结果
    // 第二个维度：该层级的第no个点
    int tmp[2][MAX_N];
    memset(tmp, 0x3F, sizeof(tmp));
    tmp[0][ano] = 0;

    // 获取dif二进制上每一个1
    for (int i = 0; (1 << i) <= dif; i++) {
        // 如果第i位是1
        if ((1 << i) & dif) {
            // 计算第alevel级别的ano个点，到第alevel + 2^i 级别的每个节点
            // 最短距离是多少
           
            // 初始化当前轮次结果
            memset(tmp[1], 0x3F, sizeof(tmp[1]));

            // 计算到当前层级的第u个节点
            for (int u = 0; u < k; u++) {
                // 从前一轮次的第v个节点过来
                for (int v = 0; v < k; v++) {
                    tmp[1][u] = min(tmp[1][u], tmp[0][v] + dat[alevel][v][u][i]);
                }
            }

            // 更新tmp[0]为tmp[1]的结果
            memcpy(tmp[0], tmp[1], sizeof(tmp[0]));

            // alevel去往后面的层级
            alevel += (1 << i);
        }
    }

    // 如果仍然是最大值，那么就是-1
    if (tmp[0][bno] == 0x3F3F3F3F) {
        cout << -1 << endl;
    }
    else {
        cout << tmp[0][bno] << endl;
    }
}

int main() {
    // 读取数据
    cin >> k >> n >> m >> q;

    // 初始化为一个很大的数值
    memset(dat, 0x3F, sizeof(dat));

    // 读取m条边信息
    int a, b, c;
    for (int i = 0; i < m; ++i) {
        cin >> a >> b >> c;

        // a所在层级
        int alevel = a / k;
        // b所在层级（一定是a+1）
        // a所在层级节点编号
        int ano = a % k;
        // b所在层级节点编号
        int bno = b % k;

        // 最后一个维度是0，代表alevel到alevel+1
        dat[alevel][ano][bno][0] = c;
    }

    // 初始化表格数据
    build();

    // 读取q次查询
    for (int i = 0; i < q; ++i) {
        cin >> a >> b;
        query(a, b);
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44