Exploration plan - VietMX's Blog

The competitors of Bubble Cup X gathered after the competition and discussed what is the best way to get to know the host country and its cities.

After exploring the map of Serbia for a while, the competitors came up with the following facts: the country has V cities which are indexed with numbers from 1 to V, and there are E bi-directional roads that connect the cites. Each road has a weight (the time needed to cross that road). There are N teams at the Bubble Cup and the competitors came up with the following plan: each of the N teams will start their journey in one of the V cities, and some of the teams share the starting position.

They want to find the shortest time T, such that every team can move in these T minutes, and the number of different cities they end up in is at least K (because they will only get to know the cities they end up in). A team doesn’t have to be on the move all the time, if they like it in a particular city, they can stay there and wait for the time to pass.

Please help the competitors to determine the shortest time T so it’s possible for them to end up in at least K different cities or print -1 if that is impossible no matter how they move.

Note that there can exist multiple roads between some cities.

Input

The first line contains four integers: V, E, N and K (1 ≤ V ≤ 600, 1 ≤ E ≤ 20000, 1 ≤ N ≤ min(V, 200), 1 ≤ K ≤ N), number of cities, number of roads, number of teams and the smallest number of different cities they need to end up in, respectively.

The second line contains N integers, the cities where the teams start their journey.

Next E lines contain information about the roads in following format: A _i B _i T _i (1 ≤ A _i, B _i ≤ V, 1 ≤ T _i ≤ 10000), which means that there is a road connecting cities A _i and B _i, and you need T _i minutes to cross that road.

Output

Output a single integer that represents the minimal time the teams can move for, such that they end up in at least K different cities or output -1 if there is no solution.

If the solution exists, result will be no greater than 1731311.

Example

input

output

Note

Three teams start from city 5, and two teams start from city 2. If they agree to move for 3 minutes, one possible situation would be the following: Two teams in city 2, one team in city 5, one team in city 3 , and one team in city 1. And we see that there are four different cities the teams end their journey at.

#include <bits/stdc++.h>
 
using namespace std;
 
template <class T> class flow_graph {
public:
static constexpr T eps = (T) 1e-9;
 
struct edge {
int to;
T c;
T f;
int rev;
};
 
vector < vector <edge> > g;
vector <int> ptr;
vector <int> d;
int n;
int st, fin;
bool modified;
 
flow_graph(int n, int st, int fin) : n (n), st (st), fin (fin) {
modified = true;
assert(0 <= st && st < n && 0 <= fin && fin < n && st != fin);
    g.resize(n);
    ptr.resize(n);
    d.resize(n);
  }
 
  void clear_flow() {
    modified = true;
    for (int i = 0; i < n; i++) {
      for (edge &e : g[i]) {
        e.f = 0;
      }
    }
  }
 
  void add(int from, int to, T forward_cap, T backward_cap) {
    modified = true;
    assert(0 <= from && from < n && 0 <= to && to < n);
    int from_size = g[from].size();
    int to_size = g[to].size();
    g[from].push_back({to, forward_cap, 0, to_size});
    g[to].push_back({from, backward_cap, 0, from_size});
  }
 
  bool expath() {
    queue <int> q({st});
fill(d.begin(), d.end(), -1);
d[st] = 0;
while (!q.empty()) {
int i = q.front();
q.pop();
for (edge &e : g[i]) {
if (e.c > e.f + eps && d[e.to] == -1) {
d[e.to] = d[i] + 1;
if (e.to == fin) {
return true;
}
q.push(e.to);
}
}
}
return false;
}
 
T dfs(int v, T w) {
if (v == fin) {
return w;
}
T r = 0;
int j = ptr[v];
while (j > 0) {
j--;
edge &e = g[v][j];
if (e.c > e.f + eps && d[e.to] == d[v] + 1) {
T ww = e.c - e.f;
if (v != st) {
ww = min(ww, w - r);
}
T t = dfs(e.to, ww);
if (t > 0) {
e.f += t;
g[e.to][e.rev].f -= t;
r += t;
if (v != st && r >= w - eps) {
return r;
}
}
}
ptr[v]--;
}
return r;
}
 
T flow;
 
T max_flow() {
if (!modified) {
return flow;
}
modified = false;
T ans = 0;
while (expath()) {
for (int i = 0; i < n; i++) {
        ptr[i] = g[i].size();
      }
      T add = dfs(st, -1);
      if (add <= eps) {
        break;
      }
      ans += add;
    }
    return flow = ans;
  }
 
  vector <bool> min_cut() {
max_flow();
vector <bool> ret(n);
for (int i = 0; i < n; i++) {
      ret[i] = (d[i] != -1);
    }
    return ret;
  }
};
 
const int N = 1234;
 
int city[N];
int g[N][N];
 
int main() {
  int v, e, n, k;
  scanf("%d %d %d %d", &v, &e, &n, &k);
  for (int i = 0; i < n; i++) {
    scanf("%d", city + i);
    city[i]--;
  }
  for (int i = 0; i < v; i++) {
    for (int j = 0; j < v; j++) {
      g[i][j] = (i == j ? 0 : (int) 1e9);
    }
  }
  for (int i = 0; i < e; i++) {
    int x, y, z;
    scanf("%d %d %d", &x, &y, &z);
    x--; y--;
    g[x][y] = min(g[x][y], z);
    g[y][x] = min(g[y][x], z);
  }
  for (int k = 0; k < v; k++) {
    for (int i = 0; i < v; i++) {
      for (int j = 0; j < v; j++) {
        g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
      }
    }
  }
  const int inf = (int) 2e6;
  int low = 0, high = inf;
  while (low < high) {
    int mid = (low + high) >> 1;
flow_graph <int> gr(n + v + 2, n + v, n + v + 1);
for (int i = 0; i < n; i++) {
      gr.add(n + v, i, 1, 0);
    }
    for (int j = 0; j < v; j++) {
      gr.add(n + j, n + v + 1, 1, 0);
    }
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < v; j++) {
        if (g[city[i]][j] <= mid) {
          gr.add(i, n + j, 1, 0);
        }
      }
    }
    if (gr.max_flow() >= k) {
high = mid;
} else {
low = mid + 1;
}
}
printf("%d\n", low == inf ? -1 : low);
return 0;
}