Submission #244707

#	Time	Username	Problem	Language	Result	Execution time	Memory
244707		santaclaus03	Toll (BOI17_toll)	C++14	10 / 100	209 ms	6392 KiB

toll

#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
using vvii = vector<vector<ii>>;

#define INF 1000000000

int main() {
    int K, n, m, o; cin >> K >> n >> m >> o;
    vvii rev(n);
    for (int i = 0; i < m; ++i) {
        int a, b, t; cin >> a >> b >> t;
        rev[b].emplace_back(t, a);
    }
    vi dist(n, INF);
    dist[0] = 0;
    for (int u = 1; u < n; ++u) {
        for (ii e : rev[u]) {
            dist[u] = min(dist[u], dist[e.second] + e.first);
        }
    }
    for (int i = 0; i < o; ++i) {
        int a, b; cin >> a >> b;
        assert(a == 0);
        int ans = dist[b];
        cout << (ans == INF ? -1 : ans) << endl;
    }
    return 0;
}

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