Submission #1092584

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092584		nguyentunglam	Train (APIO24_train)	C++17	0 / 100	1100 ms	11108 KiB

train

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

#include <cassert>
#include <cstdio>

#include <vector>


long long solve(int n, int m, int w, std::vector<int> t, std::vector<int> x, std::vector<int> y,
                std::vector<int> a, std::vector<int> b, std::vector<int> c, std::vector<int> l,
                std::vector<int> r) 
{
    #define int long long
    vector<vector<int> > adj(n);

    for (int i = 0; i < m; i++) {
        adj[x[i]].push_back(i);
    }

    #define ii pair<long long, int> 
    priority_queue<ii, vector<ii>, greater<ii> > q;

    vector<long long> f(m);

    for (int i = 0; i < m; i++) f[i] = 1e18;

    for (int &i : adj[0]) {
        long long extra = 0;
        for (int j = 0; j < w; j++) {
            if (r[j] < a[i]) extra += t[0];
        }
        q.push({f[i] = extra + c[i], i});
    }

    while (!q.empty()) {
        auto [cost, pre] = q.top(); q.pop();
        for (int &nxt : adj[y[pre]]) if (b[nxt] >= a[pre]) {
            long long extra = 0;
            for (int j = 0; j < w; j++) {
                if (b[pre] < l[j] && r[j] < a[nxt]) extra += t[y[pre]];
            }
            if (f[nxt] > f[pre] + extra + c[nxt]) {
                q.push({f[nxt] = f[pre] + extra + c[nxt], nxt});
            }
        }
    }

    long long ans = 1e18;

    for (int i = 0; i < m; i++) if (y[i] == n - 1) {
        long long extra = 0;
        for (int j = 0; j < w; j++) if (l[j] > b[i]) extra += t[n - 1];
        ans = min(ans, extra + f[i]);
    }
    #undef int long long

    if (ans == 1e18) return -1;
    return ans;

}


#ifdef ngu
signed main() {
  int N, M, W;
  assert(3 == scanf("%d %d %d", &N, &M, &W));
  std::vector<int> t(N);
  std::vector<int> x(M);
  std::vector<int> y(M);
  std::vector<int> a(M);
  std::vector<int> b(M);
  std::vector<int> c(M);
  std::vector<int> l(W);
  std::vector<int> r(W);
  for (int i = 0; i < N; i++)
    assert(1 == scanf("%d", &t[i]));
  for (int i = 0; i < M; i++)
    assert(5 == scanf("%d %d %d %d %d", &x[i], &y[i], &a[i], &b[i], &c[i]));
  for (int i = 0; i < W; i++)
    assert(2 == scanf("%d %d", &l[i], &r[i]));
  printf("%lld", solve(N, M, W, t, x, y, a, b, c, l, r));
}
#endif 

Compilation message (stderr)

train.cpp:57:16: warning: extra tokens at end of #undef directive
   57 |     #undef int long long
      |                ^~~~

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