Submission #697169

#	Time	Username	Problem	Language	Result	Execution time	Memory
697169		_martynas	Toll (BOI17_toll)	C++11	46 / 100	3035 ms	5088 KiB

toll

#include <bits/stdc++.h>

using namespace std;

struct Edge {
    int v, w;
};

const int MXN = 5e4+5;
const int INF = 1e9;

int k, n, m, o;
vector<Edge> adj[MXN];
int dist[MXN];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> k >> n >> m >> o;
    for(int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }
    for(int _ = 0; _ < o; _++) {
        fill(dist, dist+n, INF);
        int a, b; cin >> a >> b;
        dist[a] = 0;
        for(int i = a; i < b; i++) {
            for(auto e : adj[i]) {
                dist[e.v] = min(dist[e.v], dist[i]+e.w);
            }
        }
        if(dist[b] == INF) cout << "-1\n";
        else cout << dist[b] << "\n";
    }
    return 0;
}

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