Submission #244708

#	Time	Username	Problem	Language	Result	Execution time	Memory
244708		santaclaus03	Toll (BOI17_toll)	C++14	46 / 100	3073 ms	5556 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);
    }
    for (int i = 0; i < o; ++i)
    {
        int a, b;
        cin >> a >> b;
        vi dist(n, INF);
        dist[a] = 0;
        for (int u = a + 1; u < n; ++u)
        {
            for (ii e : rev[u])
            {
                dist[u] = min(dist[u], dist[e.second] + e.first);
            }
        }
        int ans = dist[b];
        cout << (ans == INF ? -1 : ans) << endl;
    }
    return 0;
}

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