Submission #701880

#	Time	Username	Problem	Language	Result	Execution time	Memory
701880		mychecksedad	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	278 ms	50212 KiB

commuter_pass

/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define PI 3.1415926535
#define pb push_back
#define all(x) x.begin(), x.end()
const int N = 1e6+100, M = 1e5+10, K = 20;
const ll LMX = 1e16;
 
int n, m, s, t, x, y;
ll dx[N], dy[N], d[N], minx[N], miny[N];
vector<array<ll, 3>> g[N];
vector<bool> vis;
 
void solve(){
  cin >> n >> m >> s >> t >> x >> y;
  for(int i = 0; i < m; ++i){
    int u, v, w; cin >> u >> v >> w;
    g[u].pb({v, w, i});
    g[v].pb({u, w, i});
  }
  vis.resize(n + 1);

  //first dijkstra
  priority_queue<pair<ll, int>> q;

  q.push({0, x});

  for(int i = 1; i <= n; ++i) dx[i] = i == x ? 0 : LMX;
  for(int i = 1; i <= n; ++i) dy[i] = i == y ? 0 : LMX;
  for(int i = 1; i <= n; ++i) d[i] = i == s ? 0 : LMX;
  for(int i = 1; i <= n; ++i) minx[i] = LMX;
  for(int i = 1; i <= n; ++i) miny[i] = LMX;

  dx[0] = 0;

  while(!q.empty()){
    int v = q.top().second; q.pop();
    if(vis[v]) continue;
    vis[v] = 1;
    for(auto U: g[v]){
      int u = U[0], w = U[1];
      if(!vis[u] && dx[u] > dx[v] + w){
        dx[u] = dx[v] + w;
        q.push({-dx[u], u});
      }
    }
  }

  fill(all(vis), 0);
  q.push({0, y});

  dy[0] = 0;

  while(!q.empty()){
    int v = q.top().second; q.pop();
    if(vis[v]) continue;
    vis[v] = 1;
    for(auto U: g[v]){
      int u = U[0], w = U[1];
      if(!vis[u] && dy[u] > dy[v] + w){
        dy[u] = dy[v] + w;
        q.push({-dy[u], u});
      }
    }
  }


  priority_queue<array<ll, 2>> Q; // dist, node, min_x_dist
  Q.push({0, s});
  d[s] = 0;
  fill(all(vis), 0);
  while(!Q.empty()){
    int v = Q.top()[1];
    Q.pop();
    if(vis[v]) continue;
    minx[v] = dx[v];
    miny[v] = dy[v];
    vis[v] = 1;
    for(auto U: g[v]){
      int u = U[0], w = U[1];
      if(vis[u] && d[v] == d[u] + w){
        minx[v] = min(minx[u], minx[v]);
        miny[v] = min(miny[u], miny[v]);
      }
      if(!vis[u] && d[u] > d[v] + w){
        d[u] = d[v] + w;
        Q.push({-d[u], u});
      }
    }
  }

  ll ans = LMX;

  queue<int> qu; qu.push(t);  
  fill(all(vis), 0);
  vis[t] = 1;
  while(!qu.empty()){
    int v = qu.front();
    qu.pop();
    ans = min(ans, minx[v] + dy[v]);
    ans = min(ans, miny[v] + dx[v]);
    for(auto U: g[v]){
      int u = U[0], w = U[1];
      if(d[u] == d[v] - w){
        if(!vis[u]){
          vis[u] = 1;
          qu.push(u);
        }
      }
    }
  }
  for(int i = 1; i <= n; ++i) ans = min(ans, dx[i] + dy[i]);
  cout << ans;
}
 
 
int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int T = 1, aa;
  // cin >> T;aa=T;
  while(T--){
    // cout << "Case #" << aa-T << ": ";
    solve();
    cout << '\n';
  }
  return 0;
 
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:123:14: warning: unused variable 'aa' [-Wunused-variable]
  123 |   int T = 1, aa;
      |              ^~

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