Submission #878311

#	Time	Username	Problem	Language	Result	Execution time	Memory
878311		1L1YA	Toll (BOI17_toll)	C++17	100 / 100	2246 ms	7860 KiB

toll

//1L1YA
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#define ll           long long
#define Pb           push_back
#define dokme(x)     cout << x << endl, exit(0)
#define pii          pair<int,int>
#define F            first
#define S            second
#define endl         '\n'
#define sep          ' '
#define all(x)       x.begin(),x.end()
#define FastIO       ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lc           id<<1
#define rc           lc|1

const ll mod=1e9+7;
const ll oo=4e18;
const int N=5e4+23;
const int lg=23;

int n,m,k,q,d[N];
vector<pii> adj[N];

int main(){
    FastIO

    cin >> k >> n >> m >> q;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin >> u >> v >> w;
        adj[v].Pb({u,w});
    }
    while(q--){
        int u,v;
        cin >> u >> v;
        for(int i=0;i<2*k;i++)
            if(u-i>=0)
                d[u-i]=mod;
        d[u]=0;
        for(int i=u+1;i<=v;i++){
            d[i]=mod;
            for(auto w: adj[i])
                d[i]=min(d[i],d[w.F]+w.S);
        }
        if(d[v]==mod)
            cout << -1 << endl;
        else
            cout << d[v] << endl;
    }

    return 0;
}

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