제출 #1273167

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273167		sexo69696969	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	439 ms	30232 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;
#ifdef local
  #include "debug.hpp"
  #define pr(...) debug(#__VA_ARGS__, __VA_ARGS__)
  #define prs(...) debug_nameless(__VA_ARGS__)
#else
  #define pr(...) 69
  #define prs(...) 69
#endif

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using i128 = __int128;
using u128 = unsigned __int128;

const i64 inf = 1e9+1;
const i64 binf = 2e13;

/*
seja o caminho S-T: a_1 a_2 ... a_n
seja o caminho U-V: b_1 b_2 ... b_m

lema: 
os vértices em comum aos dois são um subcaminho (tanto de S-T quanto de U-V)

prova:
se tem apenas um vertice em comum, isso é óbvio.
se tem dois vértices em comum, o caminho entre eles pode ser comum.
*colapsar esse caminho em ambos, pra virar um vértice*
repetir esse argumento indutivamente.

solução naive: testar todos (x, y)
solução rápida: considerar o DAG do dijktras saindo de S.

pra cada vértice x, tenho que achar algum y tal que:
1. y chegue em T.
2. distancia x->V é minima.

definimos f(x) como:
inf, se y nao chega em T
dist(x -> V), caso contrario

calcular dp[x] := min(f(v)) para todo v visto por x

no final, achar min(dp[x] + dist(U->x))
*/

struct Graph{
  int n;
  vector <vector<pair<int,int>>> adj;
  Graph(int n){
    this->n = n;
    adj.resize(n);   
  }
  void add_edge(int u, int v, int w){
    adj[u].emplace_back(v, w);
  }
  vector<i64> dijkstras(int source, vector<array<int,3>>& edges){
    vector <i64> dist(n, binf);
    dist[source] = 0;
    set <pair<i64, int>> s;
    for(int i = 0; i < n; i++){
      s.insert({dist[i], i});
    }
    while(s.size() > 0){
      auto [d, node] = *s.begin();
      s.erase(s.begin());
      for(auto [nei, w] : adj[node]){
        if(dist[node]+w < dist[nei]){
          s.erase({dist[nei], nei});
          dist[nei] = dist[node]+w;
          s.insert({dist[nei], nei});
        }
        if(dist[node]+w == dist[nei]){
          edges.push_back({node, nei, w});
        }
      }
    }
    return dist;
  }
  i64 calc(int s, int t, int u, int v, vector<i64>& dist_u, vector<i64>& dist_v){
    vector <bool> valid(n, false), vis(n, false);
    valid[t] = true;
    function <void(int)> dfs = [&](int node){
      vis[node] = true;
      for(auto [nei, w] : adj[node]){
        if(!vis[nei]){
          dfs(nei);
        }
        valid[node] = valid[node] || valid[nei];
      }
    };
    dfs(s);
    vector <array<int,3>> tmp;
    vector <i64> dp(n, binf);
    fill(vis.begin(), vis.end(), false);
    dfs = [&](int node){
      vis[node] = true;
      if(valid[node]){
        dp[node] = dist_v[node];
      }
      for(auto [nei, w] : adj[node]){
        if(!vis[nei]){
          dfs(nei);
        }
        dp[node] = min(dp[node], dp[nei]);
      }
    };
    dfs(s);
    pr(dp, valid, dist_v);
    i64 ans = binf;
    for(int i = 0; i < n; i++){
      ans = min(ans, dp[i] + dist_u[i]);
    }
    fill(dp.begin(), dp.end(), binf);
    fill(vis.begin(), vis.end(), false);
    dfs = [&](int node){
      vis[node] = true;
      if(valid[node]){
        dp[node] = dist_u[node];
      }
      for(auto [nei, w] : adj[node]){
        if(!vis[nei]){
          dfs(nei);
        }
        dp[node] = min(dp[node], dp[nei]);
      }
    };
    dfs(s);
    for(int i = 0; i < n; i++){
      ans = min(ans, dp[i] + dist_v[i]);
    }
    return ans;
  }
};
void solve(int tc){
  int n, m;
  cin >> n >> m;
  int s, t, u, v;
  cin >> s >> t >> u >> v;
  s -= 1, t -= 1, u -= 1, v -= 1;
  Graph ori(n);
  for(int i = 0; i < m; i++){
    int u, v, w;
    cin >> u >> v >> w;
    u -= 1, v -= 1;
    ori.add_edge(u, v, w);
    ori.add_edge(v, u, w);
  }
  pr("uepa");
  vector <array<int,3>> edges;
  ori.dijkstras(s, edges);
  pr(edges);
  Graph dag(n);
  for(auto [u, v, w] : edges){
    dag.add_edge(u, v, w);
  }
  vector <array<int,3>> tmp;
  auto dist_v = ori.dijkstras(v, tmp);
  auto dist_u = ori.dijkstras(u, tmp);
  pr(dist_v[u]);
  cout << min(dist_v[u], dag.calc(s, t, u, v, dist_u, dist_v)) << "\n";
}

signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0);

  int tc = 1;
  // cin >> tc;

  for(int t = 0; t < tc; t++){
    pr(t); prs(string(50, '-'));
    solve(t);
    prs(string(50, '-') + "\n");
  }

  return 0;
}

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