제출 #209014

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
209014		eriksuenderhauf	Olympic Bus (JOI20_ho_t4)	C++11	100 / 100	65 ms	8108 KiB

ho_t4

#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)(x).size()
#define trav(x, a) for (const auto& x: a)
#define pii pair<int,int>
#define st first
#define nd second
using namespace std;
typedef long long ll;
const int N = 5e4 + 5;
const ll inf = 0x1f1f1f1f1f1f1f1f;
vector<int> e[2][N], adj[N];
int U[N], V[N], C[N], D[N];
ll dp[2][2][N], dp2[2][205][205];
int n, m, par[2][2][N];
int mrk[2][2][N];
vector<int> path[2][2];

void solve(int s, int t, int i) {
  priority_queue<pii,vector<pii>,greater<pii>> pq;
  pq.push({0, s});
  for (int j = 1; j <= n; j++)
    dp[i][s>1][j] = inf;
  dp[i][s>1][s] = 0;
  while (!pq.empty()) {
    auto c = pq.top(); pq.pop();
    if (dp[i][s>1][c.nd] != c.st)
      continue;
    for (int j: e[i][c.nd]) {
      int v = U[j]^V[j]^c.nd;
      if (dp[i][s>1][v] > c.st + C[j]) {
        dp[i][s>1][v] = c.st + C[j];
        par[i][s>1][v] = j;
        pq.push({dp[i][s>1][v], v});
      }
    }
  }
  if (dp[i][s>1][t] == inf)
    return;
  int u = t;
  while (u != s) {
    int j = par[i][s>1][u];
    mrk[i][s>1][j] = 1;
    path[i][s>1].pb(u);
    u = U[j]^V[j]^u;
  }
  path[i][s>1].pb(u);
  reverse(path[i][s>1].begin(), path[i][s>1].end());
}

ll calc(int j, int i) {
  int mi = n+1;
  for (int l = 0; l+1 < sz(path[0][j]); l++) {
    if (U[i] == path[0][j][l] && path[0][j][l+1] == V[i]) {
      mi = l;
      break;
    }
  }
  ll ret = inf;
  for (int l = 0; l <= mi; l++)
    for (int r = mi+1; r < sz(path[0][j]); r++)
      ret = min(ret, dp[0][j][path[0][j][l]] + dp2[j][path[0][j][l]][path[0][j][r]] + dp[1][j^1][path[0][j][r]]);
  return ret;
}

int main() {
  memset(dp, 0x1f, sizeof dp);
  memset(dp2, 0x1f, sizeof dp2);
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= m; i++) {
    scanf("%d %d %d %d", U+i, V+i, C+i, D+i);
    e[0][U[i]].pb(i);
    e[1][V[i]].pb(i);
  }
  for (int i = 0; i < 2; i++) {
    solve(1, n, i);
    solve(n, 1, i);
  }
  for (int t = 0; t < 2; t++) {
    for (int i = 1; i <= m; i++) if (!mrk[0][t][i])
        dp2[t][U[i]][V[i]] = min(dp2[t][U[i]][V[i]], 1ll*C[i]);
    for (int i = 1; i <= n; i++)
      dp2[t][i][i] = 0;
    for (int k = 1; k <= n; k++)
      for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
          dp2[t][i][j] = min(dp2[t][i][j], dp2[t][i][k] + dp2[t][k][j]);
  }
  ll x1 = dp[0][0][n], x2 = dp[0][1][1];
  ll ans = x1 + x2;
  for (int i = 1; i <= m; i++) {
    bool f1 = mrk[0][0][i], f2 = mrk[0][1][i];
    ll c1 = min(x1, dp[0][0][V[i]] + C[i] + dp[1][1][U[i]]);
    ll c2 = min(x2, dp[0][1][V[i]] + C[i] + dp[1][0][U[i]]);
    if (f1 && f2)
      ans = min(ans, calc(0,i) + calc(1,i) + D[i]);
    else if (f1)
      ans = min(ans, calc(0,i) + c2 + D[i]);
    else if (f2)
      ans = min(ans, calc(1,i) + c1 + D[i]);
    else
      ans = min(ans, c1 + c2 + D[i]);
  }
  if (ans >= inf)
    ans = -1;
  printf("%I64d\n", ans);
}

컴파일 시 표준 에러 (stderr) 메시지

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:106:24: warning: format '%d' expects argument of type 'int', but argument 2 has type 'll {aka long long int}' [-Wformat=]
   printf("%I64d\n", ans);
                        ^
ho_t4.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n, &m);
   ~~~~~^~~~~~~~~~~~~~~~~
ho_t4.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d", U+i, V+i, C+i, D+i);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 63 / 63