제출 #1364145

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1364145		takoshanava	Toll (BOI17_toll)	C++20	100 / 100	119 ms	176540 KiB

toll

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fs first
#define sc second
using namespace std;

const int N = 50005, LOG = 18, INF = 1e9;
int k, n, m, q, dp[N][LOG][5][5], ans[5][5], tmp[5][5];

signed main() {
    cin >> k >> n >> m >> q;

    int bl = (n + k - 1) / k;

    for(int i = 0; i < bl; i++){
        for(int j = 0; j < LOG; j++){
            for(int x = 0; x < k; x++){
                for(int y = 0; y < k; y++){
                    dp[i][j][x][y] = INF;
                }
            }
        }
    }

    for(int i = 0; i < m; i++){
        int a, b, t;
        cin >> a >> b >> t;
        dp[a / k][0][a % k][b % k] = min(dp[a / k][0][a % k][b % k], t);
    }

    for(int j = 1; j < LOG; j++){
        for(int i = 0; i + (1 << j) < bl; i++){
            for(int x = 0; x < k; x++){
                for(int y = 0; y < k; y++){
                    dp[i][j][x][y] = INF;
                    for(int z = 0; z < k; z++){
                        dp[i][j][x][y] = min(dp[i][j][x][y],
                            dp[i][j - 1][x][z] + dp[i + (1 << (j - 1))][j - 1][z][y]);
                    }
                }
            }
        }
    }

    while(q--){
        int a, b; cin >> a >> b;
        int cur = a / k, tar = b / k;

        for(int x = 0; x < k; x++){
            for(int y = 0; y < k; y++){
                ans[x][y] = INF;
            }
        }

        for(int x = 0; x < k; x++) ans[x][x] = 0;

        for(int j = LOG - 1; j >= 0; j--){
            if(cur + (1 << j) <= tar){
                for(int x = 0; x < k; x++){
                    for(int y = 0; y < k; y++){
                        tmp[x][y] = INF;
                    }
                }

                for(int x = 0; x < k; x++){
                    for(int y = 0; y < k; y++){
                        for(int z = 0; z < k; z++){
                            tmp[x][y] = min(tmp[x][y], ans[x][z] + dp[cur][j][z][y]);
                        }
                    }
                }

                for(int x = 0; x < k; x++){
                    for(int y = 0; y < k; y++){
                        ans[x][y] = tmp[x][y];
                    }
                }

                cur += (1 << j);
            }
        }

        if(ans[a % k][b % k] >= INF) cout << -1 << endl;
        else cout << ans[a % k][b % k] << endl;
    }
}

• 서브태스크 1: 7 / 7
• 서브태스크 2: 10 / 10
• 서브태스크 3: 8 / 8
• 서브태스크 4: 31 / 31
• 서브태스크 5: 44 / 44