oj.uz

Submission #875388

# Submission time Handle Problem Language Result Execution time Memory
875388 2023-11-19T12:45:58 Z mgl_diamond Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 135 ms 13096 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
 
#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l); i>=(r); --i)
#define fore(x, v) for(auto &x : v)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define file "input"

template<class T> bool minimize(T &a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> bool maximize(T &a, T b) { if (a < b) { a = b; return 1; } return 0; }

void setIO() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  if (fopen(file".inp", "r")) {
    freopen(file".inp", "r", stdin);
    freopen(file".out", "w", stdout);
  }
}

const int N = 202;
int n, m;
vector<ii> adj[N];
vector<pair<int, ii>> radj[N];

int dp[N][N][2];
bool process[N][N][2];

struct node {
  int w, u, v;
  bool used;
  node(int _w=0, int _u=0, int _v=0, bool _used=0) : w(_w), u(_u), v(_v), used(_used) {}
  friend bool operator < (const node a, const node b) { return a.w > b.w; }
};
priority_queue<node> pq;

int main() {
  setIO();

  cin >> n >> m;
  foru(i, 1, m) {
    int u, v, w, d;
    cin >> u >> v >> w >> d;
    adj[u].emplace_back(v, w);
    radj[v].push_back({u, {w, d}});
  }

  memset(dp, 0x3f, sizeof(dp));
  dp[1][n][0] = 0;
  pq.push(node(0, 1, n, 0));

  while (!pq.empty()) {
    auto st = pq.top();
    pq.pop();

    int dist = st.w, u = st.u, v = st.v;
    bool used = st.used;
    if (process[u][v][used]) continue;
    process[u][v][used] = 1;

    if (u != n) 
    fore(x, adj[u]) {
      int to = x.fi, w = x.se;
      if (minimize(dp[to][v][used], dist + w)) pq.push(node(dp[to][v][used], to, v, used));
    }

    if (v != 1)
    fore(x, adj[v]) {
      int to = x.fi, w = x.se;
      if (minimize(dp[u][to][used], dist + w)) pq.push(node(dp[u][to][used], u, to, used));
    }

    if (v == 1)
    fore(x, radj[u]) {
      int to = x.fi, w = x.se.fi, d = x.se.se;
      if (minimize(dp[to][v][1], dist + w + d)) pq.push(node(dp[to][v][1], to, v, 1));
    }

    if (u == n)
    fore(x, radj[v]) {
      int to = x.fi, w = x.se.fi, d = x.se.se;
      if (minimize(dp[u][to][1], dist + w + d)) pq.push(node(dp[u][to][1], u, to, 1));
    }

    if (u == v) 
    fore(x, radj[v]) {
      int to = x.fi, w = x.se.fi, d = x.se.se;
      if (minimize(dp[to][to][1], dist + 2 * w + d)) pq.push(node(dp[to][to][1], to, to, 1));
    }
  }

  int ans = min(dp[n][1][0], dp[n][1][1]);
  if (ans < (int)1e9) cout << ans;
  else cout << -1;
}

Compilation message

ho_t4.cpp: In function 'void setIO()':
ho_t4.cpp:22:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     freopen(file".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
ho_t4.cpp:23:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     freopen(file".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1492 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 16 ms 1496 KB Output is correct
4 Correct 18 ms 1516 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Incorrect 0 ms 604 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 13096 KB Output is correct
2 Incorrect 129 ms 12124 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1496 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 54 ms 3852 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 63 ms 4564 KB Output is correct
6 Incorrect 1 ms 604 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1492 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 16 ms 1496 KB Output is correct
4 Correct 18 ms 1516 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Incorrect 0 ms 604 KB Output isn't correct
8 Halted 0 ms 0 KB -