제출 #1305744

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1305744		Sofiatpc	Toll (BOI17_toll)	C++20	100 / 100	66 ms	18424 KiB

toll

#include <bits/stdc++.h>

using namespace std;

#define sz(v) (int)v.size()
const int MAXN = 5*1e4+5, MAX = 15, INF = 1e9;
vector<int> adj[MAXN], w[MAXN];
int mn[MAX+5][5][MAXN];

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int k,n,m,q; cin>>k>>n>>m>>q;
    
    for(int i = 0; i <= MAX; i++)
        for(int md = 0; md < k; md++)
            for(int j = 0; j < n; j++)mn[i][md][j] = INF;

    for(int i = 0; i < m; i++){
        int a,b,c; cin>>a>>b>>c;
        adj[a].push_back(b); w[a].push_back(c);
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < sz(adj[i]); j++){
            int viz = adj[i][j];
            mn[0][viz%k][i] = min( mn[0][viz%k][i], w[i][j] );
        }
    }

    for(int i = 1; i <= MAX; i++)
        for(int md = 0; md < k; md++)
            for(int j = 0; j < n; j++){
                for(int md2 = 0; md2 < k; md2++){
                    mn[i][md][j] = min( mn[i][md][j], mn[i-1][md2][j] + mn[i-1][md][ (j/k)*k + (1<<(i-1))*k + md2 ] );
                }
            }
    
    while(q--){
        int a,b; cin>>a>>b;

        int qtd = b/k-a/k;

        int cur[5]; for(int md = 0; md < k; md++)cur[md] = INF; cur[a%k] = 0;

        a = (a/k)*k;
        for(int i = MAX; i >= 0; i--)
            if(qtd & (1<<i)){
                //cout<<i<<" "<<a<<"!!\n";
                int nxt[5]; for(int md = 0; md < k; md++)nxt[md] = INF;

                for(int md = 0; md < k; md++)
                    for(int md2 = 0; md2 < k; md2++){
                        nxt[md] = min(nxt[md], cur[md2] + mn[i][md][ a+ md2] );

                        //cout<<md<<" "<<md2<<" = "<<cur[md2]<<" "<<mn[i][md][ a + md2]<<" "<<a + md2 <<"\n";
                    }
                a += (1<<i)*k;

                for(int md = 0; md < k; md++)cur[md] = nxt[md];
            }

        if(cur[b%k] == INF)cout<<"-1\n";
        else cout<<cur[b%k]<<"\n";
    }
}   

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