Submission #2333020

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int inf = (1<<28);

bool _dfs(vector<vector<int> > &g, int n, int m, int u, vector<int> &X, vector<int> &Y, vector<int> &used) {
  if(used[u]) return false;
  used[u] = true;
  for (int k=0; k<g[u].size(); k++) {
    int v = g[u][k] - n;
    if(Y[v] == -1) { X[u] = v; Y[v] = u; return true; }
    else if(_dfs(g, n, m, Y[v], X, Y, used)) { X[u] = v; Y[v] = u; return true; }
  }
  return false;
}

int bipartite_matching(vector<vector<int> > &g, int n, int m) {
  vector<int> X(n, -1), Y(m, -1);
  for (int i=0; i<n; i++) {
    vector<int> used(n, false);
    _dfs(g, n, m, i, X, Y, used);
  }
  return n - count(X.begin(), X.end(), -1);
}

int main() {
  int n, m, kn, qn;
  cin >> n >> m;
  int g[n][n];
  for (int i=0; i<n; i++) for (int j=0; j<n; j++) g[i][j] = inf;
  for (int i=0; i<n; i++) g[i][i] = 0;
  for (int i=0; i<m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    u--; v--;
    g[u][v] = g[v][u] = w;
  }
  for (int i=0; i<n; i++)
    for (int j=0; j<n; j++)
      for (int k=0; k<n; k++)
        g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
  cin >> kn;
  vector<int> k(kn);
  for (int i=0; i<kn; i++) { cin >> k[i]; k[i]--; }
  cin >> qn;
  vector<int> q(qn);
  for (int i=0; i<qn; i++) { cin >> q[i]; q[i]--; }

  int ll=0, rr=inf;
  for (int _=0; _<50; _++) {
    int w = (ll+rr)/2, t = 0;

    vector<vector<int> > bg(k.size()-1+q.size(), vector<int>());
    for (int i=0; i<k.size()-1; i++) {
      if (g[k[i]][k[i+1]] <= w) continue;
      t++;
      for (int j=0; j<q.size(); j++) {
        if (g[q[j]][k[i+1]] <= w) {
          bg[i].push_back(j+k.size()-1);
          bg[j+k.size()-1].push_back(i);
        }
      }
    }

    if (bipartite_matching(bg, k.size()-1, q.size()) == t)
      rr = w;
    else
      ll = w;
  }
  cout << rr << endl;

  return 0;
}

Submission Info

Judge Result