oj.uz

답안 #1092583

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1092583 2024-09-24T14:02:13 Z nguyentunglam 은하철도 (APIO24_train) C++17
0 / 100
 1000 ms 15196 KB 
// #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) 
{
    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]);
    }

    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

Subtask #1
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Correct.
2 Correct 1 ms 344 KB Correct.
3 Incorrect 1 ms 348 KB Wrong Answer.
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 10572 KB Correct.
2 Correct 66 ms 15196 KB Correct.
3 Correct 0 ms 348 KB Correct.
4 Correct 8 ms 3948 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 141 ms 10584 KB Correct.
7 Correct 0 ms 344 KB Correct.
8 Execution timed out 1031 ms 14204 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 10572 KB Correct.
2 Correct 66 ms 15196 KB Correct.
3 Correct 0 ms 348 KB Correct.
4 Correct 8 ms 3948 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 141 ms 10584 KB Correct.
7 Correct 0 ms 344 KB Correct.
8 Execution timed out 1031 ms 14204 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Correct.
2 Correct 1 ms 344 KB Correct.
3 Incorrect 1 ms 348 KB Wrong Answer.
4 Halted 0 ms 0 KB -