Submission #246323

#	Time	Username	Problem	Language	Result	Execution time	Memory
246323		Nightlight	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	578 ms	27344 KiB

commuter_pass

#include <bits/stdc++.h>
#define pii pair<long long, int>
using namespace std;

int N, M;
int S, T, U, V;
vector<pii> adj[100005];
vector<int> child[100005];
long long best[2][100005];//0 -> S, 1 -> T
long long dist[2][100005];//0 -> U, 1 -> V
long long dp[2][100005];
priority_queue<pii, vector<pii>, greater<pii>> pq;
long long opt, ans = 4e18;

void find_opt(int init, int id) {
  pq.emplace(0, init);
  best[id][init] = 0;
  int u, v;
  long long len, w;
  while(!pq.empty()) {
    u = pq.top().second;
    len = pq.top().first;
    pq.pop();

    for(pii now : adj[u]) {
      v = now.second;
      w = now.first;
      if(best[id][v] > len + w) {
        best[id][v] = len + w;
        pq.emplace(best[id][v], v);
      }
    }
  }
}

void make_DAG() {
  opt = best[0][T];
  int u, v;
  long long w;
  for(u = 1; u <= N; u++) {
    for(pii now : adj[u]) {
      v = now.second;
      w = now.first;
      if(best[0][u] + w + best[1][v] <= opt) child[u].emplace_back(v);
    }
  }
}

void find_dist(int init, int id) {
  pq.emplace(0, init);
  dist[id][init] = 0;
  int u, v;
  long long len, w;
  while(!pq.empty()) {
    u = pq.top().second;
    len = pq.top().first;
    pq.pop();

    for(pii now : adj[u]) {
      v = now.second;
      w = now.first;
      if(dist[id][v] > len + w) {
        dist[id][v] = len + w;
        pq.emplace(dist[id][v], v);
      }
    }
  }
}

long long depe(int id, int u) {
  if(u == T) return dist[id][T];
  if(dp[id][u] != -1) return dp[id][u];
  long long res = dist[id][u];
  for(int v : child[u]) {
    res = min(res, depe(id, v));
  }
  return dp[id][u] = res;
}

void solve() {
  find_opt(S, 0);
  find_opt(T, 1);
  make_DAG();
  find_dist(U, 0);
  find_dist(V, 1);

  ans = dist[0][V];
  for(int i = 1; i <= N; i++) {
    if(child[i].size() == 0) continue;
    ans = min(ans, dist[0][i] + depe(1, i));
    ans = min(ans, dist[1][i] + depe(0, i));
  }
  printf("%lld\n", ans);
  cin >> N;
}

int main() {
  memset(dp, -1, sizeof(dp));
  memset(best, 0x3f3f3f3f, sizeof(best));
  memset(dist, 0x3f3f3f3f, sizeof(dist));
  scanf("%d %d %d %d %d %d", &N, &M, &S, &T, &U, &V);
  int u, v, w;
  for(int i = 1; i <= M; i++) {
    scanf("%d %d %d", &u, &v, &w);
    adj[u].emplace_back(w, v);
    adj[v].emplace_back(w, u);
  }
  solve();
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d %d %d", &N, &M, &S, &T, &U, &V);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:104:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &u, &v, &w);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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