Submission #1258972

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258972		islam_2010	Toll (BOI17_toll)	C++20	100 / 100	1741 ms	4600 KiB

toll

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

const int sz = 5e4+5;
const int inf = 1e9+7;

vector<pair<int, int>> g[sz];
vector<int> dis(sz, inf);


signed main(){

    int k, n, m, q;
    cin >> k >> n >> m >> q;
    for(int i = 0; i < m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        g[v].push_back({u, w});
    }
    while (q--){
        
        int u, v;
        cin >> u >> v;
        dis[u] = 0;
        for(int i = u; i <= v; i++){
            for(auto node: g[i]){
                dis[i] = min(dis[i], dis[node.first] + node.second);
            }
        }
        if(dis[v] == inf){
            cout << -1 << endl;
        }else {
            cout << dis[v] << endl;
        }
        for(int i = u; i <= v; i++){
            dis[i] = inf;
        }
        
    }

}

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