제출 #1185410

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1185410		asli_bg	Autobus (COCI22_autobus)	C++20	70 / 70	631 ms	208776 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long

typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<bool> vb;

#define fi first
#define se second
#define pb push_back

#define mid (l+r)/2
#define all(x) x.begin(),x.end()
#define FOR(i,a) for(int i=0;i<(a);i++)
#define FORE(i,a,b) for(int i=(a);i<(b);i++)

#define cont(x) for(auto el:x) cout<<el<<' ';cout<<endl;
#define contp(x) for(auto el:x) cout<<el.fi<<'-'<<el.se<<' ';cout<<endl;
#define sp <<" "<<

#define DEBUG(x) cout<<(#x) sp x<<endl

const int INF=1e18;
const int MAXN=75;

int n,m,k,q;

vii adj[MAXN];
int d[MAXN][MAXN][MAXN*MAXN];
int tut[MAXN][MAXN];

int say;

void dij(int bas){
    set<pair<int,pii>> s;
    s.insert({0,{0,bas}});

    FORE(i,1,n+1){
        FORE(j,0,say+1){
            d[bas][i][j]=INF;
        }
    }
    d[bas][bas][0]=0;

    while(!s.empty()){
        auto el=*s.begin();
        s.erase(el);

        int nd=el.se.se;
        int kk=el.se.fi;

        if(kk>=k) continue;

        for(auto [kom,cost]:adj[nd]){
            if(d[bas][kom][kk+1]>d[bas][nd][kk]+cost){
                if(d[bas][kom][kk+1]!=INF) s.erase({d[bas][kom][kk+1],{kk+1,kom}});
                d[bas][kom][kk+1]=d[bas][nd][kk]+cost;
                s.insert({d[bas][kom][kk+1],{kk+1,kom}});
            }
        }
    }
}

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

    map<pii,int> edg;

    cin>>n>>m;
    FOR(i,m){
        int a,b,c;
        cin>>a>>b>>c;
        if(edg[{a,b}]==0) edg[{a,b}]=c;
        else edg[{a,b}]=min(edg[{a,b}],c);
    }

    say=0;
    for(auto el:edg){
        int a=el.fi.fi;
        int b=el.fi.se;
        int c=el.se;

        say++;

        adj[a].pb({b,c});
    }

    assert(say<=n*n);

    cin>>k>>q;

    k=min(k,n);

    FORE(i,1,n+1) dij(i);

    while(q--){
        int a,b;
        cin>>a>>b;
        int res=INF;
        FOR(i,min(k,say)+1){
            res=min(res,d[a][b][i]);
        }
        cout<<(res!=INF?res:-1)<<endl;
    }
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 15 / 15