Submission #833398

#	Time	Username	Problem	Language	Result	Execution time	Memory
833398		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	253 ms	28504 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;
  debug({
    for(int i = 1; i <= n; i++)
      cerr << "i = " << i << " : " << par[i] << '\n';
  });

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

  debug({
    for(Edge e : edges)
      cerr << e.u << ' ' << e.v << ' ' << e.w << '\n';
  });

  cout << dijkstra(s2, t2).first << '\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: 0 / 24
• Subtask 4: 0 / 45