제출 #756742

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
756742		NeroZein	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	759 ms	37560 KiB

commuter_pass

#include "bits/stdc++.h"
#define int long long 
using namespace std;
 
#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif
 
using T = pair<int, int>;
 
const int N = 100005;
 
int n, m;
int s, t;
int uu, vv;
int cnt;
vector<int> pr[N];
set<pair<int, int>> se; 
vector<pair<int, int>> g[N]; 
 
vector<int> dijk (int src) {
  cnt++; 
  vector<bool> vis(n + 1, false);
  vector<int> cost(n + 1, 1e16); 
  cost[src] = 0;
  priority_queue<T, vector<T>, greater<T>> pq;
  pq.emplace(0, src);
  while (!pq.empty()) {
    auto [c, v] = pq.top();
    pq.pop();
    if (vis[v] == true) {
      continue;
    }
    vis[v] = true; 
    for (auto [u, w] : g[v]) {
      if (vis[u]) {
        continue;
      }
      if (cnt > 3 && se.count({v, u})) {
        w = 0; 
      } 
      if (c + w < cost[u]) {
        cost[u] = c + w;
        pq.emplace(cost[u], u); 
        pr[u].clear(); 
      }
      if (cnt == 3 && c + w == cost[u]) {
        pr[u].push_back(v); 
      }
    }
  }
  return cost;
}
 
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  cin >> s >> t;
  cin >> uu >> vv;
  for(int i = 0; i < m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w);
  }
  auto cuu1 = dijk(uu);
  auto cvv1 = dijk(vv);
  auto cs = dijk(s);
  vector<bool> vis(n + 1); 
  function<void(int)> Dfs = [&](int v) {
    vis[v] = true; 
    for (int u : pr[v]) {
      se.emplace(u, v); 
      if (!vis[u]) {
        Dfs(u);
      }
    }
  }; 
  Dfs(t); 
  auto cuu2 = dijk(uu); 
  auto cvv2 = dijk(vv); 
  int ans = cuu2[vv];
  for (int i = 1; i <= n; ++i) {
    ans = min(ans, cuu1[i] + cvv2[i]); 
    ans = min(ans, cuu2[i] + cvv1[i]); 
  }
  cout << ans << '\n'; 
  return 0;
}

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