Submission #557548

#	Time	Username	Problem	Language	Result	Execution time	Memory
557548		fatemetmhr	Toll (BOI17_toll)	C++17	46 / 100	3076 ms	10412 KiB

toll

// `Be name khoda` //

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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


const int maxn5 = 2e5 + 10;
const int inf   = 1e9;

int dis[maxn5];
vector <pair<int, int>> jda[maxn5];

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

    int k, n, m, q; cin >> k >> n >> m >> q;
    for(int i = 0; i < m; i++){
        int a, b, t; cin >> a >> b >> t;
        jda[b].pb({a, t});
    }
    for(int i = 0; i < q; i++){
        int a, b; cin >> a >> b;
        fill(dis, dis + n + 4, inf);
        dis[b] = 0;
        for(int i = b; i > a; i--){
            for(auto [u, t] : jda[i])
                dis[u] = min(dis[u], dis[i] + t);
        }
        if(dis[a] == inf)
            dis[a] = -1;
        cout << dis[a] << '\n';
    }
}

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