Submission #875388

#	Time	Username	Problem	Language	Result	Execution time	Memory
875388		mgl_diamond	Olympic Bus (JOI20_ho_t4)	C++17	0 / 100	135 ms	13096 KiB

ho_t4

#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 (stderr)

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
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63