Submission #1362754

#	Time	Username	Problem	Language	Result	Execution time	Memory
1362754		opeleklanos	Train (APIO24_train)	C++20	0 / 100	44 ms	12312 KiB

train

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#include "train.h"

#define ll long long
#define INF (ll)100000000000000000000

struct route{
    ll t1;
    ll t0;
    ll from;
    ll dest;
    ll cost;
    ll totalCost;
};

vector<vector<ll>> adj;

vector<pair<ll, ll>> meals;

vector<vector<ll>> dp;

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){

    adj.assign(N, {});

    vector<route> paths;
    for(ll i = 0; i<M; i++){
        adj[X[i]].push_back(i);
        adj[Y[i]].push_back(i);
        paths.push_back({B[i], A[i], X[i], Y[i], C[i], INF});
    }
    for(ll i = 0; i<W; i++) meals.push_back({L[i], R[i]});
    sort(meals.begin(), meals.end());

    for(ll i = 0; i<M; i++){
        if(paths[i].from == 0) paths[i].totalCost = paths[i].cost;
    }

    for(ll i = 0; i<M; i++){
        for(auto j : adj[paths[i].from]){
            if(paths[j].dest == paths[i].from && paths[j].t1 <= paths[i].t0){
                paths[i].totalCost = min(paths[i].totalCost, paths[j].totalCost + paths[j].cost);
            }
        }
    }

    ll ans = INF;
    for(ll i = 0; i<M; i++){
        if(paths[i].dest == N-1) ans = min(ans, paths[i].totalCost);
    }

    return ans;
}

Compilation message (stderr)

train.cpp:35:56: warning: integer constant is too large for its type
   35 |         paths.push_back({B[i], A[i], X[i], Y[i], C[i], INF});
      |                                                        ^~~
train.cpp:52:14: warning: integer constant is too large for its type
   52 |     ll ans = INF;
      |              ^~~

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