제출 #1123090

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1123090		asli_bg	Toll (BOI17_toll)	C++20	7 / 100	3095 ms	13632 KiB

toll

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

#define int long long

#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sp <<' '<<
#define pb push_back

#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(a) for(auto el:a) cout<<el<<' '; cout<<endl;
#define contp(a) for(auto el:a) cout<<el.fi<<'-'<<el.se<<' ';cout<<endl;

#define DEBUG(x) cout<<#x sp ":" sp x<<endl;

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef long long ll;

#define mid (l+r)/2

#define topla(x,y) ((x%MOD)+(y%MOD))%MOD
#define carp(x,y) ((x%MOD)*(y%+MOD))%MOD

const int MAXN=5e4+5;
const int INF=1e10+5;;

int k,n,m,o;

vii adj[MAXN];
int deg[MAXN];
map<int,int> dist[MAXN];

void dfs(int nd,int d,int bas){

    if(dist[nd][bas]==0) dist[nd][bas]=d;
    else dist[nd][bas]=min(dist[nd][bas],d);

    //dist[nd][bas]=d; //bastan bana mesafe

    for(auto el:adj[nd]){
        int kom=el.fi;
        int cost=el.se;
        dfs(kom,d+cost,bas);
    }
}

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

    //there is only one path from a to b

    cin>>k>>n>>m>>o;
    FOR(i,m){
        int a,b,t;
        cin>>a>>b>>t;
        a++;b++;
        adj[a].pb({b,t});
        deg[b]++;
    }

    FORE(i,1,n+1){
        if(deg[i]==0){
            dfs(i,1,i);
        }
    }

    while(o--){
        int a,b;
        cin>>a>>b;
        a++;b++;

        int cev=INF;

        for(auto el:dist[a]){
            int bas=el.fi;
            int cost=el.se;
            if(dist[b][bas]==0) continue;
            if(cost>dist[b][bas]) continue;
            cev=min(cev,dist[b][bas]-cost);
        }

        cout<<(cev==INF?-1:cev)<<endl;
    }
}       

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