Submission #1110868

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110868		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	451 ms	48364 KiB

commuter_pass

#include<bits/stdc++.h>

using namespace std;
#define ll long long
const int maxn = 4e5 + 5;

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

vector<pair<int, int>> g[maxn];
ll dist[2][maxn];
bool vis[maxn];

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 <= 4 * 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(auto [v, w] : g[u]){
      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;
    g[u].push_back({v, w});
    g[v].push_back({u, w});
    
    g[u + 3 * n].push_back({3 * n + v, w}); 
    g[v + 3 * n].push_back({3 * n + u, w}); 
  }

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

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

  for(int i = 1; i <= n; i ++){
    g[i].push_back({n + i, 0});
    g[n + i].push_back({3 * n + i, 0});
    g[2 * n + i].push_back({3 * n + i, 0});
    g[i].push_back({2 * n + i, 0});
  }

  while(q.size()){
    int u = q.front(); q.pop();
    if(vis[u]) continue;
    vis[u] = 1;
    for(auto [v, w] : g[u]){
      if(v > n) continue;
      if(vis[v]) continue; 
      if(dist[0][u] + dist[1][v] + w == dist[1][S] || dist[1][u] + dist[0][v] + w == dist[1][S]){
        g[n + u].push_back({n + v, 0});
        q.push(v);
      }
    }
  }

  q.push(T);

  for(int i = 0; i <= n; i ++) vis[i] = 0;

  while(q.size()){
    int u = q.front(); q.pop();
    if(vis[u]) continue;
    vis[u] = 1;
    for(auto [v, w] : g[u]){
      if(v > n) continue;
      if(vis[v]) continue; 
      if(dist[1][u] + dist[0][v] + w == dist[1][S] || dist[0][u] + dist[1][v] + w == dist[1][S]){
        g[2 * n + u].push_back({2 * n + v, 0});
        q.push(v);
      }
    }
  }

  dij(V, dist[1]);

  cout << dist[1][U + 3 * n];
}

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