Submission #1258964

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258964		islam_2010	Toll (BOI17_toll)	C++20	0 / 100	3095 ms	3388 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);


void dijkstra(int node){
    dis[node] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.push({0, node});
    while ( !q.empty()){
        auto [c, curr] = q.top();
        q.pop();

        for(auto [v, w]: g[curr]){
            if(dis[v] > dis[curr] + w){
                dis[v] = dis[curr] + w;
                q.push({dis[v], v});
            }
        }
    }
}

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[u].push_back({v, w});
    }
    while (q--){
        
        int u, v;
        cin >> u >> v;
        
        for(int i = u; i <= v; i++){
            for(auto node: g[i]){
                dis[node.first] = min(dis[node.first], dis[i] + node.second);
            }
        }dijkstra(u);
        if(dis[v] == inf){
            cout << -1 << endl;
        }else {
            cout << dis[v] << endl;
        }
        for(int i = u; i <= v; i++){
            dis[i] = inf;
        }
        
    }

}

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