제출 #1185396

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1185396		asli_bg	Autobus (COCI22_autobus)	C++20	0 / 70	4 ms	584 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];
int tut[MAXN][MAXN];

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

    FORE(i,1,n+1) d[bas][i]=INF;
    d[bas][bas]=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]>d[bas][nd]+cost){
                if(d[bas][kom]!=INF) s.erase({d[bas][kom],{tut[bas][kom],kom}});
                d[bas][kom]=d[bas][nd]+cost;
                tut[bas][kom]=kk+1;
                s.insert({d[bas][kom],{tut[bas][kom],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);
    }

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

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

    cin>>k>>q;

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

    while(q--){
        int a,b;
        cin>>a>>b;
        cout<<(d[a][b]!=INF?d[a][b]:-1)<<endl;
    }
}

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