Submission #1307217

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307217		kaloyan	Toll (BOI17_toll)	C++20	100 / 100	1984 ms	4620 KiB

toll

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

const int MAXN = 50000 + 10;
const int INF = 1e9 + 10;

int k, n, m, q;

int dp[MAXN];
std::vector<std::pair<int, int>> g[MAXN];

void solve()
{
    std::cin >> k >> n >> m >> q;

    for(int i = 1 ; i <= m ; ++i)
    {
        int x, y, z;
        std::cin >> x >> y >> z;
        x += 1, y += 1;
        g[x].push_back({y, z});
    }

    for(int i = 1 ; i <= q ; ++i)
    {
        int x, y;
        std::cin >> x >> y;
        
        x += 1, y += 1;
        if(x > y)
        {
            std::swap(x, y);
        }
        
        for(int i = x ; i <= y ; ++i)
        {
            dp[i] = INF;
        }

        dp[x] = 0;
        for(int i = x ; i <= y ; ++i)
        {
            for(auto [to, w] : g[i])
            {
                dp[to] = std::min(dp[to], dp[i] + w);
            }
        }

        std::cout << (dp[y] != INF ? dp[y] : -1) << "\n";
    }
}

void fastIO()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
}

int main()
{
    fastIO();
    solve();
    
    return 0;
}

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