Submission #197103

#	Time	Username	Problem	Language	Result	Execution time	Memory
197103		quocnguyen1012	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	603 ms	19856 KiB

commuter_pass

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

const int maxn = 1e5 + 5;

vector<pair<int, ll>> adj[maxn];
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
int N, M, S, T, U, V;
vector<ll> ds, dt, du, dv;
ll dist[maxn];

vector<ll> dijk(int st)
{
  vector<ll> d;
  d.resize(N + 5);
  fill_n(&d[0], N + 5, 1e18);
  d[st] = 0;
  pq.push(mp(0, st));
  while (pq.size()){
    auto now = pq.top(); pq.pop();
    if (now.fi != d[now.se]) continue;
    //cerr << now.se << '\n';
    for (auto & v : adj[now.se]){
      if (d[v.fi] > now.fi  + v.se){
        d[v.fi] = now.fi + v.se;
        pq.push(mp(d[v.fi], v.fi));
      }
    }
  }
  return d;
}

ll solve(void)
{
  vector<int> p;
  for (int i = 1; i <= N; ++i){
    p.pb(i);
    dist[i] = du[i];
  }
  sort(p.begin(), p.end(), [](const int & x, const int & y){
    return ds[x] < ds[y];
  });
  ll res = 1e18;
  for (int i = 0; i < N; ++i){
    int u = p[i];
    //cerr << u << '\n';
    for (auto & v : adj[u]){
      if (ds[u] + v.se + dt[v.fi] == ds[T]){
        dist[v.fi] = min(dist[v.fi], dist[u]);
      }
    }
    //cerr << u << ' ' << dist[u] << ' ' << dv[u] << '\n';
    res = min(res, dist[u] + dv[u]);
  }
  return res;
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if (fopen("A.INP", "r")){
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  }
  cin >> N >> M >> S >> T >> U >> V;
  while (M--){
    int u, v, w;
    cin >> u >> v >> w;
    adj[u].pb(mp(v, w)); adj[v].pb(mp(u, w));
  }
  ds = dijk(S); dt = dijk(T); du = dijk(U); dv = dijk(V);
  assert(ds[T] == dt[S]); assert(du[V] == dv[U]);
  ll res = solve();
  swap(S, T); swap(ds, dt);
  res = min(res, solve());
  cout << res << '\n';
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:69:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.INP", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:70:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.OUT", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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