Submission #1194767

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194767		Mousa_Aboubaker	Train (APIO24_train)	C++20	5 / 100	45 ms	13236 KiB

train

#include "train.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>;

long long solve(int N, int M, int W, vector<int> T, vector<int> X, vector<int> Y,
                vector<int> A, vector<int> B, vector<int> C, vector<int> L,
                vector<int> R)
{
    // the second subtask
    vector adj(N, vector<tuple<int, int, int, int>>()); // x[i] = {y[i], b[i], c[i]}
    for(int i = 0; i < M; i++)
        adj[X[i]].push_back({Y[i], B[i], C[i], A[i]});
    pqg<tuple<ll, int, int>> pq; // cost, lst, u
    map<pair<int, int>, ll> dp;
    pq.push({0, 0, 0});
    while(not pq.empty())
    {
        auto [cost, lst, u] = pq.top();
        pq.pop();

        if(dp.find({u, lst}) != dp.end() and dp[{u, lst}] <= cost)
            continue;
        dp[{u, lst}] = cost;
        if(u == N - 1)
            break;
        for(auto [y, b, c, a]: adj[u])
        {
            if(a >= lst)
            {
                pq.push({cost + c, b, y});
            }
        }
    }
    ll res = 1e18;
    for(auto [f, s]: dp)
    {
        if(f.first == N - 1)
        {
            if(res > s)
                res = s;
        }
    }
    if(res == 1e18)
        res = -1;
    return res;
}

• Subtask 1: 0 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60