Submission #1110866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110866		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	255 ms	36592 KiB

commuter_pass

#include<bits/stdc++.h>

using namespace std;
#define ll long long
const int maxn = 2e5;

int n, m;
int S, T, U, V;

struct Edge{
  int u, v, c;
  bool in;
  int getO(const int &x = 0) const{
      return x ^ u ^ v;
  }
}e[maxn];

vector<int> g[maxn];
ll dist[3][100005];
bool vis[100005];

void dij(int s, ll f[]){
  priority_queue<pair<ll, int>, vector<pair<ll,int>>, greater<pair<ll,int>>> q;
  for(int i = 1; i <= n; i ++) f[i] = 1e18;

  q.push({0, s}); f[s] = 0;
  while(q.size()){
    auto [du, u] = q.top();
    q.pop();
    if(du != f[u]) continue;
    for(int i : g[u]){
      int v = e[i].getO(u);
      int w = e[i].c;
      if(f[v] > du + w){
        f[v] = du + w;
        q.push({f[v], v});
      }
    }
  }
}

int main(){
  cin >> n >> m >> S >> T >> U >> V;

  for(int i = 1; i <= m; i ++){
    int u, v, w; cin >> u >> v >> w;
    e[i] = {u, v, w, 0};
    g[u].push_back(i);
    g[v].push_back(i);
  }

  dij(S, dist[0]);
  dij(T, dist[1]);

  queue <int> q;
  q.push(S);

  while(q.size()){
    int u = q.front(); q.pop();
    if(vis[u]) continue;
    vis[u] = 1;
    for(int i : g[u]){
      int v = e[i].getO(u);
      int w = e[i].c;
      if(dist[0][u] + dist[1][v] + w == dist[1][S] || dist[0][v] + dist[1][u] + w == dist[0][T]){
        e[i].in = 1;
        q.push(v);
      }
    }
  }

  for(int i = m; i >= 1; i --){
    int u = e[i].u;
    int v = e[i].v;
    if(e[i].in){
        e[++ m] = {u, v, 0, 0};
        g[u].push_back(m);
        g[v].push_back(m);
    }
  }


  dij(V, dist[2]);

  cout << dist[2][U];
}

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