제출 #924529

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
924529		Faisal_Saqib	Toll (BOI17_toll)	C++17	7 / 100	3013 ms	3452 KiB

toll

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// #define int long long
const int N=5e4+2;
vector<pair<int,int>> ma[N];//,query[N];
// vector<int> block[N];
// int index[N];
// bool vis[N];
// int ans[N];
int Dist[N][6][6];
int ans[6][6];
int ans_[6][6];
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int k,n,m,q;
    cin>>k>>n>>m>>q;
    for(int j=0;j<m;j++)
    {
        int a,b,t;
        cin>>a>>b>>t;
        ma[a].push_back({b,t});
    }
    // for(int lp=0;lp<q;lp++)
    // {
    //     int x,y;
    //     cin>>x>>y;
    //     query[x].push_back({y,lp});
    // }
    // for(int i=0;i<n;i++)
    // {
    //     index[i]=block[i/k].size();
    //     block[(i/k)].push_back(i);
    // }
    // for(int l=0;l<n;l++)
    //     for(int ind=0;ind<k;ind++)
    //         for(int p=0;p<k;p++)
    //             Dist[l][ind][p]=1e9;
    // for(int i=0;i<n;i++)
    //     Dist[(i/k)][i%k][i%k]=we;
    for(int lp=0;lp<q;lp++)
    {
        int x,y;
        cin>>x>>y;
        int cur_block=x/k;
        int block_to=y/k;
        for(int i=0;i<k;i++)
            for(int j=0;j<k;j++)
                ans_[i][j]=1e9;
        for(int i=0;i<k;i++)
            for(int j=0;j<k;j++)
                ans[i][j]=((i==j)?0:1e9);
        while(cur_block<block_to)
        {
            for(int j=0;j<k;j++)
            {
                for(int i=0;i<k;i++)
                {
                    for(auto& [adj,we]:ma[(cur_block*k)+i])
                    {
                        ans_[i][adj%k]=min(ans_[i][adj%k],ans[j][i]+we);
                    }
                }
            }
            for(int j=0;j<k;j++)
            {
                for(int i=0;i<k;i++)
                {
                    ans[i][j]=ans_[i][j];
                    ans_[i][j]=1e9;
                    // cout<<ans[i][j]<<' ';
                }
                // cout<<'\n';
            }
            // cout<<"Change\n";
            cur_block++;
        }
        int ansp=1e9;
        for(int i=0;i<k;i++)
        {
            ansp=min(ansp,ans[i][y%k]);
        }
        if(ansp==1e9)
        {
            cout<<-1<<'\n';
        }
        else
        {
            cout<<ansp<<'\n';
        }
    }
    return 0;
}

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