제출 #1284364

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284364		lmquan	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	238 ms	21072 KiB

commuter_pass

#define taskname "cumm"
#include <bits/stdc++.h>
using namespace std;
const int kN = 1e5 + 1;
const long long kInf = 5e18;

int n, m, s, t, u, v;
long long dp[2][kN];
vector<pair<int, long long>> g[kN];

void Dijkstra(int s, vector<long long>& x, int i, vector<long long>& f) {
  priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
  x.resize(n + 1, kInf);
  x[s] = 0;
  pq.push({x[s], s});
  vector<bool> y(n + 1, false);
  while (!pq.empty()) {
    auto a = pq.top();
    pq.pop();
    if (y[a.second]) {
      continue;
    }
    y[a.second] = true;
    for (auto [b, w] : g[a.second]) {
      if (x[b] > x[a.second] + w) {
        x[b] = x[a.second] + w;
        if (i != -1) {
          dp[i][b] = min(dp[i][a.second], f[a.second]);
        }
        pq.push({x[b], b});
      } else if (x[a.second] + w == x[b] && i != -1) {
        dp[i][b] = min(dp[i][b], min(dp[i][a.second], f[a.second]));
      }
    }
  }
}

int main() {
  if (fopen(taskname".txt", "r")) {
    freopen(taskname".txt", "r", stdin);
    freopen(taskname".out", "w", stdout);
  }
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> m >> s >> t >> u >> v;
  for (int i = 1; i <= m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    g[a].push_back({b, c});
    g[b].push_back({a, c});
  }

  for (int i = 0; i <= n; i++) {
    dp[0][i] = dp[1][i] = kInf;
  }

  vector<long long> du, dv, ds, dt, k = {0};
  Dijkstra(u, du, -1, k);
  Dijkstra(v, dv, -1, k);
  Dijkstra(s, ds, 0, dv);
  Dijkstra(t, dt, 1, dv);

  long long result = du[v];
  for (int i = 1; i <= n; i++) {
    if (ds[i] + dt[i] == ds[t]) {
      result = min(result, min(dp[0][i], dp[1][i]) + du[i]);
    }
  }

  cout << result;

  return 0;
}

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

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:40:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     freopen(taskname".txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:41:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     freopen(taskname".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45