Submission #833511

#	Time	Username	Problem	Language	Result	Execution time	Memory
833511		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	575 ms	43988 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// using ld = long double;
#define all(x) begin(x), end(x)
#ifdef LOCAL
#define debug(...) __VA_ARGS__;
#else
#define debug(...)
#endif

template<class A, class B> ostream& operator<<(ostream& os, const pair<A, B> &p);
template<class T> ostream& operator<<(ostream& os, const vector<T> &v);
template<class T, size_t N> ostream& operator<<(ostream& os, const array<T, N> &v);

template<class A, class B>
ostream& operator<<(ostream& os, const pair<A, B> &p) {
  return os << '(' << p.first << ',' << p.second << ')';
}
 
template<class T>
ostream& operator<<(ostream& os, const vector<T> &v) {
  os << '{'; bool fs = 1;
  for(auto &i : v) { if(!fs) os << ','; os << i; fs = 0; }
  return os << '}';
}

template<class T, size_t N>
ostream& operator<<(ostream& os, const array<T, N> &v) {
  os << '{'; bool fs = 1;
  for(auto &i : v) { if(!fs) os << ','; os << i; fs = 0; }
  return os << '}';
}

void init() {
}
 
void solve(int tt = 0) {
  int n, m; cin >> n >> m;
  int s, t; cin >> s >> t;
  int s2, t2; cin >> s2 >> t2;
  struct Edge {
    int u, v, w;
    Edge() {}
    Edge(int u, int v, int w) : u(u), v(v), w(w) {}
    inline int get_other(int x) {
      return x == u ? v : u;
    };
  };
  vector<Edge> edges;
  vector adj(n+1, vector<int>());
  for(int i = 0; i < m; i++) {
    int u, v, w; cin >> u >> v >> w;
    adj[u].push_back(edges.size());
    adj[v].emplace_back(edges.size());
    edges.push_back(Edge(u, v, w));
  }
  const ll INF = 1e18;
  const auto dijkstra = [&](int s, int t) {
    vector<ll> dist(n+1, INF);
    vector<int> vis(n+1, 0);
    vector<vector<pair<int, int>>> par(n+1);
    using state = pair<ll, int>;
    priority_queue<state, vector<state>, greater<state>> pq;
    pq.push({dist[s] = 0, s});
    while(!pq.empty()) {
      int u = pq.top().second; pq.pop();
      if(u == t) break;
      if(vis[u]) continue;
      vis[u] = 1;
      for(int i : adj[u]) {
        int v = edges[i].get_other(u);
        int w = edges[i].w;
        if(vis[v]) continue;
        if(dist[v] > dist[u] + w) {
          par[v].clear();
          par[v].emplace_back(u, i);
          pq.push({dist[v] = dist[u] + w, v});
        } else if(dist[v] == dist[u] + w) {
          par[v].emplace_back(u, i);
        }
      }
    }
    return make_pair(dist[t], par);
  };

  vector par = dijkstra(s, t).second;

  vector<vector<pair<int, int>>> go(n+1);

  vector<int> ind;
  {
    vector<int> vis(n+1, 0);
    const auto dfs = [&](const auto &dfs, int u) -> void {
      vis[u] = 1;
      ind.push_back(u);
      for(auto &[v, _] : par[u]) if(!vis[v]) {
        dfs(dfs, v);
      }
    };
    dfs(dfs, t);
  }
  for(int i : ind) go[i] = par[i];

  vector<vector<pair<int, int>>> rev(n+1);
  for(int u = 1; u <= n; u++) {
    for(auto &[v, i] : go[u]) {
      rev[v].emplace_back(u, i);
    }
  }
  debug(cerr << "ind = " << ind << '\n');
  debug({
    cerr << "go = " << '\n';
    for(int i = 1; i <= n; i++)
      cerr << "i = " << i << " : " << go[i] << '\n';
  });
  debug({
    cerr << "rev = " << '\n';
    for(int i = 1; i <= n; i++)
      cerr << "i = " << i << " : " << rev[i] << '\n';
  });

  const auto dijkstra2 = [&](int s, int t) {
    // dist[u][stat{0,1,2,3}]
    vector dist(n+1, vector<ll>(4, INF));
    vector vis(n+1, vector<int>(4, 0));
    using state = tuple<ll, int, int>;
    priority_queue<state, vector<state>, greater<state>> pq;
    pq.push({dist[s][0] = 0, s, 0});
    while(!pq.empty()) {
      auto [d, u, stat] = pq.top(); pq.pop();
      if(vis[u][stat]) continue;
      debug(cerr << u << ' ' << stat << " -> " << d << '\n');
      vis[u][stat] = 1;
      if(stat == 0 || stat == 3) {
        for(int i : adj[u]) {
          int v = edges[i].get_other(u);
          int w = edges[i].w;
          if(vis[v][stat]) continue;
          if(dist[v][stat] > d + w) {
            pq.push({dist[v][stat] = d + w, v, stat});
          }
        }
        if(stat == 0 && !go[u].empty() && dist[u][1] > d) {
          pq.push({dist[u][1] = d, u, 1});
        }
        if(stat == 0 && !rev[u].empty() && dist[u][2] > d) {
          pq.push({dist[u][2] = d, u, 2});
        }
      } else if(stat == 1) { // normal
        for(auto [v, _] : go[u]) {
          if(vis[v][stat]) continue;
          if(dist[v][stat] > d) {
            pq.push({dist[v][stat] = d, v, stat});
          }
        }
        if(dist[u][3] > d) {
          pq.push({dist[u][3] = d, u, 3});
        }
      } else { // rev
        for(auto [v, _] : rev[u]) {
          if(vis[v][stat]) continue;
          if(dist[v][stat] > d) {
            pq.push({dist[v][stat] = d, v, stat});
          }
        }
        if(dist[u][3] > d) {
          pq.push({dist[u][3] = d, u, 3});
        }
      }
    }
    debug(cerr << dist[t] << '\n');
    return *min_element(dist[t].begin(), dist[t].end());
  };

  cout << dijkstra2(s2, t2) << '\n';
}

void reset() {
}
 
int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; // cin >> t;
  init();
  for(int i = 1; i <= t; i++) solve(i), reset();
  return 0;
}

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