Submission #362629

#	Time	Username	Problem	Language	Result	Execution time	Memory
362629		JerryLiu06	Toll (BOI17_toll)	Java	100 / 100	2483 ms	368100 KiB

toll

import java.io.*;
import java.util.*;

// Solution Notes: Split the graph into N / K "layers" with K nodes each. Notice that each edge leads from one layer to the
// next layer. Now, let DP[a][b][x][y] denote the minimum cost of a path between nodes Ka + x and Kb + y. For any triple 
// a < b < c, the following recurrence holds: DP[a][c][x][y] = MIN_{z in [0, K)} (DP[a][b][x][z] + DP[b][c][z][y]). This is
// known as the (min, +) product. Now, we have to note that there are N^2 K^2 states, so we have to reduce the number of
// states. This motivates us to, instead of storing DP[a][b][x][y], we can store only DP[a][a + 2^i][x][y] for each a, i, x,
// y. Then we can find the value of DP[A / K][B / K][A % K][B % K] in O(K^3 (N + O) log N) complexity.

public class toll {

    static int K, N, M, O; static int[][][][] DP = new int[50010][20][5][5];

    static int[][] temp = new int[5][5]; static int[][] ans = new int[5][5];

    static final int INF = Integer.MAX_VALUE / 3;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        K = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        O = Integer.parseInt(st.nextToken());

        for (int i = 0; i < 50010; i++) for (int j = 0; j < 20; j++) {
            for (int k = 0; k < 5; k++) Arrays.fill(DP[i][j][k], INF);
        }
        for (int i = 0; i < M; i++) { st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int W = Integer.parseInt(st.nextToken());

            DP[A / K][0][A % K][B % K] = W;
        }
        for (int j = 1; j < 20; j++) for (int i = 0; i + (1 << j) < (N + K - 1) / K; i++) {
            combine(DP[i][j], DP[i][j - 1], DP[i + (1 << (j - 1))][j - 1]);
        }
        for (int i = 0; i < O; i++) { st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());

            for (int j = 0; j < 5; j++) Arrays.fill(ans[j], INF);

            for (int j = 0; j < 5; j++) ans[j][j] = 0;

            int jump = (B / K) - (A / K); int curLev = A / K;

            for (int j = 0; j < 20; j++) if ((jump & (1 << j)) > 0) {
                for (int k = 0; k < 5; k++) Arrays.fill(temp[k], INF);

                combine(temp, ans, DP[curLev][j]); 

                for (int k = 0; k < 5; k++) for (int l = 0; l < 5; l++) ans[k][l] = temp[k][l];

                curLev += (1 << j);
            }
            System.out.println(ans[A % K][B % K] == INF ? -1 : ans[A % K][B % K]);
        }
    }
    static void combine(int[][] res, int[][] A, int[][] B) {
        for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) for (int k = 0; k < 5; k++) {
            res[i][j] = Math.min(res[i][j], A[i][k] + B[k][j]);
        }
    }
}

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