제출 #1130032

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1130032		m_bezrutchka	Commuter Pass (JOI18_commuter_pass)	C++20	31 / 100	350 ms	39384 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

#define int long long

typedef pair<int, int> pii;
typedef pair<int, pii> pip;
typedef pair<pii, int> ppi;
typedef pair<pii, pii> ppp;

const int LLINF = 2e18 + 10;
const int MAXN = 2e5 + 10;

int n;
vector<pii> adj[MAXN];

vector<int> dijkstra(int s) {
  vector<int> dist(n + 1, LLINF);
  vector<int> mrk(n + 1, false);
  priority_queue<pii> pq;
  dist[s] = 0;
  pq.push({0, s});

  while (!pq.empty()) {
    int v = pq.top().second;
    pq.pop();
    if (mrk[v]) continue;
    mrk[v] = true;

    for (auto [w, c]: adj[v]) {
      if (!mrk[w] && dist[w] >= dist[v] + c) {
        dist[w] = dist[v] + c;
        pq.push({-dist[w], w});
      }
    }
  }

  return dist;
}

int dc[4][MAXN];
bool mrkc[4][MAXN];
priority_queue<pip> pqc;

void refresh_edge(int tv, int v, int tw, int w, int c) {
  if (!mrkc[tw][w] && dc[tw][w] >= dc[tv][v] + c) {
    dc[tw][w] = dc[tv][v] + c;
    pqc.push({-dc[tw][w], {tw, w}});
  }
}

int commuter_pass(int s, int t) {
  for (int i = 1; i <= n; i++) {
    dc[0][i] = dc[1][i] = dc[2][i] = dc[3][i] = LLINF;
  }
  dc[0][s] = 0;
  pqc.push({0, {0, s}});

  while (!pqc.empty()) {
    auto p = pqc.top();
    int v = p.second.second, t = p.second.first;
    pqc.pop();
    if (mrkc[t][v]) continue;
    mrkc[t][v] = true;

    for (auto [w, c]: adj[v]) {
      if (c < 0) {
        if (c == -1 && (t == 0 || t == 1)) {
          refresh_edge(t, v, 1, w, 0);
        }
        if (c == -2 && (t == 0 || t == 2)) {
          refresh_edge(t, v, 2, w, 0);
        }
      } else {
        refresh_edge(t, v, t, w, c);
      }
    }
  }

  return min({ dc[0][t], dc[1][t], dc[2][t], dc[3][t] });
}

void solve() {
  int m, house, school, book_u, book_v;
  cin >> n >> m >> house >> school >> book_u >> book_v;

  vector<ppi> edges;
  for (int i = 0; i < m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    adj[a].push_back({b, c});
    adj[b].push_back({a, c});
    edges.push_back({{a, b}, c});
  }

  vector<int> dh = dijkstra(house);
  vector<int> ds = dijkstra(school);

  for (auto &e: edges) {
    int a = e.first.first, b = e.first.second, c = e.second;
    if (dh[a] + c + ds[b] == dh[school]) {
      adj[a].push_back({b, -1});
      adj[b].push_back({a, -2});
    }
    if (dh[b] + c + ds[a] == dh[school]) {
      adj[a].push_back({b, -2});
      adj[b].push_back({a, -1});
    }
  }

  cout << commuter_pass(book_u, book_v) << endl;
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  solve();
  return 0;
}

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