제출 #1156766

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1156766		Ludissey	Toll (BOI17_toll)	C++20	0 / 100	814 ms	10100 KiB

toll

#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define int long long
using namespace std;

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int k,n,m,o; cin >> k >> n >> m >> o;
    vector<vector<pair<int,int>>> neigh(n+k);
    vector<vector<pair<int,int>>> ineigh(n+k);
    for (int i = 0; i < m; i++)
    {
        int a,b,t; cin >> a >> b >> t;
        neigh[a].push_back({b,t});
        ineigh[b].push_back({a,t});
    }
    int sq=sqrt(n);
    vector<vector<pair<pair<int,int>,int>>> query(sq+1);
    for (int i = 0; i < o; i++)
    {
        int a,b; cin >> a >> b;
        query[a/sq].push_back({{a,b},i});
    }
    vector<int> ans(o,-1);
    for (int i = 0; i < sq; i++)
    {
        sort(all(query[i]),[](auto a, auto b){ 
            if(a.first.second==b.first.second) return a<b;
            return a.first.second<b.first.second;
        });
        int mx=((i+1)*sq)-1;
        mx=((mx+k-1)/k)*k-1;
        vector<vector<int>> dist(k,vector<int>(n+k,1e12));
        vector<vector<int>> visited(k,vector<int>(n+k,0));
        for (int j = mx-k+1; j <= mx; j++)
        {
            int jk=j-(mx-k+1);
            priority_queue<pair<int,pair<int,int>>> pq;
            pq.push({0,{j,2}});
            dist[jk][j]=0;
            while(!pq.empty()){
                int x=pq.top().second.first; int tp=pq.top().second.second; pq.pop();
                if(visited[jk][x]) continue;
                visited[jk][x]=true;
                if(tp==0||tp==2){
                    for (auto u : neigh[x])
                    {
                        if(dist[jk][u.first]>dist[jk][x]+u.second){
                            dist[jk][u.first]=dist[jk][x]+u.second;
                            pq.push({-dist[jk][u.first],{u.first,0}});
                        }
                    }
                }
                if(tp==1||tp==2){
                    for (auto u : ineigh[x])
                    {
                        if(dist[jk][u.first]>dist[jk][x]+u.second){
                            dist[jk][u.first]=dist[jk][x]+u.second;
                            pq.push({-dist[jk][u.first],{u.first,1}});
                        }
                    }
                }
            }
        }
        vector<int> sdist(n+k,1e12);
        vector<bool> svisit(n+k,0);
        for (auto u : query[i])
        {
            int a=u.first.first,b=u.first.second; 
            if(b<mx-k+1){
                queue<int> toc;
                priority_queue<pair<int,int>> pq;
                pq.push({0,a});
                sdist[a]=0;
                while(!pq.empty()){
                    int x=pq.top().second; pq.pop();
                    if(svisit[x]) continue;
                    svisit[x]=true;
                    toc.push(x);
                    for (auto u : neigh[x])
                    {
                        if(u.first>b) continue;
                        if(sdist[u.first]>sdist[x]+u.second){
                            sdist[u.first]=sdist[x]+u.second;
                            pq.push({-sdist[u.first],u.first});
                        }
                    }
                }
                if(sdist[a]==1e12) sdist[a]=-1;
                ans[u.second]=sdist[a];
                while(!toc.empty()){
                    int u=toc.front(); toc.pop();
                    sdist[u]=1e12;
                    svisit[u]=false;
                }
            }else{
                int mn=1e12;
                for (int j = mx-k+1; j <= mx; j++)
                {
                    mn=min(mn,dist[j-(mx-k+1)][a]+dist[j-(mx-k+1)][b]);
                }
                if(mn>=1e12){
                    mn=-1;
                }
                ans[u.second]=mn;
            }
        }
        
    }
    for (int j = 0; j < o; j++) cout << ans[j] << "\n";
    return 0;
}

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