Submission #1057704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057704		adrielcp	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	426 ms	36236 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int INF = 1e18;
#define debug(x) cout << #x << " " << (x) << endl;

void g(vector<int> &a) {
  for (auto el : a) cout << el << ", ";
  cout << endl;
}

int n,m,s,t,u,v;
vector<vector<pair<int, int>>> adj;
vector<int> djikstra(int start) {
  vector<int> dp(n, INF);
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
  pq.push({0, start});

  // vector<int> vis(n);

  while (!pq.empty()) {
    auto [cost, node] = pq.top();pq.pop();
    if (dp[node] == INF) {
      dp[node] = cost;
      for (auto [children, w] : adj[node]) pq.push({cost + w, children}); 
    }
  }

  return dp;
}

int ans = INF;
#define info tuple<int,int,int>
vector<int> distU, distV;

void djikstra2(int start, int end) {
  vector<vector<int>> dp(n, vector<int>(2, INF));
  vector<int> dist(n, INF);
  
  priority_queue<info, vector<info>, greater<info>> pq;
  pq.push({0, start, -1});

  while (!pq.empty()) {
    auto [cost, node, par] = pq.top();pq.pop();

    int par0 = par == -1 ? INF : dp[par][0];
    int par1 = par == -1 ? INF : dp[par][1];

    if (dist[node] == INF) {
      dist[node] = cost;
      dp[node][0] = min(distU[node], par0);
      dp[node][1] = min(distV[node], par1);
      for (auto [children, w] : adj[node]) {
        pq.push({cost+w, children, node});
      }
    } else if (cost == dist[node]) {
      if (min(distU[node], par0) + min(distV[node], par1) <= dp[node][0] + dp[node][1]) {
        dp[node][0] = min(distU[node], par0);
        dp[node][1] = min(distV[node], par1);
      }
    }
  }

  ans = min(ans, dp[end][0] + dp[end][1]);
}

void solve() {
  cin>>n>>m>>s>>t>>u>>v;s--;t--;u--;v--;
  adj = vector<vector<pair<int, int>>>(n, vector<pair<int, int>>());

  for (int i = 0; i < m; i++) {
    int x,y,w;cin>>x>>y>>w;x--;y--;
    adj[x].push_back({y, w});
    adj[y].push_back({x, w});  
  }

  distU = djikstra(u);
  distV = djikstra(v);

  // DAG from S
  ans = distU[v];

  djikstra2(s, t);
  djikstra2(t, s);

  cout << ans << endl;
}

int32_t main() {
  solve();
  return 0;
}

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