Submission #1009806

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009806		makanhulia	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	322 ms	262144 KiB

commuter_pass

#include<bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define ppi pair<pii, int> 
#define pu push_back
#define fi first
#define se second

using namespace std;
const int maxn = 1e5;
const int inf = 1e15;

int n, m, s, t, u, v;
int a[maxn+5], b[maxn+5], c[maxn+5], du[maxn+5], dv[maxn+5], ds[maxn+5], dt[maxn+5], dpsv[maxn+5], dptv[maxn+5];
vector<pii> adj[maxn+5];
priority_queue<ppi, vector<ppi>, greater<ppi>> p;
priority_queue<pii, vector<pii>, greater<pii>> q;

signed main() {
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin >> n >> m >> s >> t >> u >> v;
  for (int i=1; i<=m; i++) {
    cin >> a[i] >> b[i] >> c[i];
    adj[a[i]].pu({b[i], c[i]});
    adj[b[i]].pu({a[i], c[i]});
  }
  for (int i=1; i<=n; i++) {
    du[i] = dv[i] = ds[i] = dt[i] = inf;
  }
  // dijkstra u to all nodes and v to all nodes
  du[u] = 0;
  q.push({0, u});
  while (!q.empty()) {
    int now = q.top().se, dis = q.top().fi; q.pop();
    if (dis > du[now]) continue;
    for (auto i: adj[now]) {
      if (dis + i.se >= du[i.fi]) continue;
      du[i.fi] = dis + i.se;
      q.push({du[i.fi], i.fi});
    }
  }
  dv[v] = 0;
  q.push({0, v});
  while (!q.empty()) {
    int now = q.top().se, dis = q.top().fi; q.pop();
    if (dis > dv[now]) continue;
    for (auto i: adj[now]) {
      if (dis + i.se >= dv[i.fi]) continue;
      dv[i.fi] = dis + i.se;
      q.push({dv[i.fi], i.fi});
    }    
  }
  
  // do the same for nodes s and t
  ds[s] = 0;
  q.push({0, s});
  while (!q.empty()) {
    int now = q.top().se, dis = q.top().fi; q.pop();
    if (dis > ds[now]) continue;
    for (auto i: adj[now]) {
      if (dis + i.se >= ds[i.fi]) continue;
      ds[i.fi] = dis + i.se;
      q.push({ds[i.fi], i.fi});
    }    
  }
  dt[t] = 0;
  q.push({0, t});
  while (!q.empty()) {
    int now = q.top().se, dis = q.top().fi; q.pop();
    if (dis > dt[now]) continue;
    for (auto i: adj[now]) {
      if (dis + i.se >= dt[i.fi]) continue;
      dt[i.fi] = dis + i.se;
      q.push({dt[i.fi], i.fi});
    }    
  }
  
  for (int i=1; i<=n; i++) {
    dpsv[i] = dptv[i] = dv[i];
  }
  
  // update
  q.push({0, t});
  while (!q.empty()) {
    int now = q.top().se, dis = q.top().fi; q.pop();
    for (auto i: adj[now]) {
      if (dis + i.se > dt[i.fi] || ds[i.fi] + dt[i.fi] > ds[t]) continue;
//      cout << i.fi << " to " << now << " is an edge in a shortest path from s-t" << endl;
      dptv[i.fi] = min(dptv[i.fi], dptv[now]);
      q.push({dt[i.fi], i.fi});
    }    
  }

  q.push({0, s});
  while (!q.empty()) {
    int now = q.top().se, dis = q.top().fi; q.pop();
    for (auto i: adj[now]) {
      if (dis + i.se > ds[i.fi] || ds[i.fi] + dt[i.fi] > ds[t]) continue;
//      cout << i.fi << " to " << now << " is an edge in a shortest path from s-t" << endl;
      dpsv[i.fi] = min(dpsv[i.fi], dpsv[now]);
      q.push({ds[i.fi], i.fi});
    }    
  }
//
//  for (int i=1; i<=n; i++) {
//    cout << "dv[" << i << "]: " << dv[i] << endl;
//  }
//  
  int ans = du[v];
  for (int i=1; i<=n; i++) {
    if (ds[i] + dt[i] > ds[t]) continue;
    ans = min(ans, du[i] + min(dpsv[i], dptv[i])); 
  }
  cout << ans << endl;
  return 0;
}

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