Submission #244713

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

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