D - Disruption of Communication Network Editorial /

Time Limit: 5 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

ある地域には N 個の基地局があり、基地局間を結ぶ M 本の双方向通信回線が設置されています。各通信回線にはデータの伝送にかかる遅延時間が定められています。基地局は 1 から N まで、通信回線は 1 から M まで番号が付けられています。j 番目の通信回線は基地局 u_j と基地局 v_j を双方向に結び、遅延時間は w_j です。なお、通信網は連結とは限りません。

青木君はこの通信網に対して妨害工作を行うことを計画しています。青木君は M 本の通信回線の中からちょうど K 本を選んで切断します（K = 0 の場合は何も切断しません）。切断された通信回線は使用できなくなり、残った M - K 本の通信回線のみを使ってデータを伝送することになります。

この通信網には、高橋君が管理する重要な通信ペアが Q 組あります。i 番目 (1 \leq i \leq Q) の通信ペアは基地局 s_i と基地局 t_i の間の通信です。なお、同じ基地局の組が複数の通信ペアとして現れることもあります。

切断後の通信網において、基地局 s_i から基地局 t_i への最短伝送時間を d(s_i, t_i) と定義します。基地局 s_i から基地局 t_i へ到達する経路が存在しない場合は d(s_i, t_i) = +\infty とします（切断前から到達不可能な場合も同様です）。

高橋君はすべての通信ペアの伝送時間を一定以上に保ちたいと考えています。そのため、Q 組の通信ペアのうち最短伝送時間が最も小さいペアが通信網全体のボトルネックとなります。これを切断後の通信網の 耐性値 と呼び、

\min_{i=1}^{Q} d(s_i, t_i)

と定義します。

青木君の目的は、ちょうど K 本の通信回線を切断する方法をうまく選ぶことで、この耐性値をできるだけ大きくする（＝高橋君にとって最も不利な状況を作り出す）ことです。すなわち、求める値は

\max_{\text{切断方法}} \min_{i=1}^{Q} d(s_i, t_i)

です。ここで最大化は、M 本の通信回線からちょうど K 本を選んで切断するすべての方法にわたってとります。

この最大値を求めてください。

制約

  • 2 \leq N \leq 40
  • 1 \leq M \leq 17
  • 0 \leq K \leq M
  • 1 \leq Q \leq 40
  • 1 \leq u_j, v_j \leq N (1 \leq j \leq M)
  • u_j \neq v_j (1 \leq j \leq M)（自己ループはない）
  • 1 \leq w_j \leq 10^6 (1 \leq j \leq M)
  • 1 \leq s_i, t_i \leq N (1 \leq i \leq Q)
  • s_i \neq t_i (1 \leq i \leq Q)
  • 同じ基地局の組を結ぶ通信回線は高々 1 本である（多重辺はない）
  • 入力はすべて整数である

入力

N M K Q
u_1 v_1 w_1
u_2 v_2 w_2
\vdots
u_M v_M w_M
s_1 t_1
s_2 t_2
\vdots
s_Q t_Q
  • 1 行目には、基地局の数 N 、通信回線の数 M 、切断する回線の数 K 、重要な通信ペアの数 Q が、スペース区切りで与えられる。
  • 2 行目から M + 1 行目では、各通信回線の情報が与えられる。
  • 1 + j 行目 (1 \leq j \leq M) では、j 番目の通信回線が結ぶ基地局 u_j , v_j およびその遅延時間 w_j がスペース区切りで与えられる。
  • M + 2 行目から M + 1 + Q 行目では、重要な通信ペアの情報が与えられる。
  • M + 1 + i 行目 (1 \leq i \leq Q) では、i 番目の通信ペアの基地局 s_i , t_i がスペース区切りで与えられる。

出力

切断する通信回線の選び方を最適にしたときの耐性値の最大値を 1 行で出力せよ。最大値が +\infty の場合、すなわち、ある切断方法によって Q 組すべての通信ペアについて s_i から t_i へ到達不可能にできる場合は、代わりに INF と出力せよ。

入力例 1

4 4 1 2
1 2 3
2 3 4
1 3 10
3 4 2
1 3
1 4

出力例 1

10

入力例 2

3 2 2 1
1 2 5
2 3 7
1 3

出力例 2

INF

入力例 3

8 10 3 5
1 2 5
2 3 6
3 4 2
4 5 8
5 6 3
6 7 7
7 8 4
1 8 20
2 6 10
3 7 9
1 5
2 8
1 4
5 8
3 6

出力例 3

23

入力例 4

15 17 5 10
1 2 4
2 3 8
3 4 15
4 5 16
5 6 23
6 7 42
7 8 7
8 9 9
9 10 11
10 11 13
11 12 17
12 13 19
13 14 21
14 15 25
1 5 30
3 10 14
6 15 18
1 15
2 14
4 11
5 9
7 13
1 8
3 12
6 10
2 14
9 15

出力例 4

INF

入力例 5

40 1 1 40
1 2 1000000
1 2
1 3
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40

出力例 5

INF

Score : 400 pts

Problem Statement

In a certain region, there are N base stations, connected by M bidirectional communication links. Each communication link has a defined delay time for data transmission. The base stations are numbered from 1 to N, and the communication links are numbered from 1 to M. The j-th communication link connects base station u_j and base station v_j bidirectionally, with a delay time of w_j. Note that the communication network is not necessarily connected.

Aoki is planning a sabotage operation on this communication network. Aoki selects exactly K links out of the M communication links and cuts them (if K = 0, nothing is cut). Cut communication links become unusable, and data must be transmitted using only the remaining M - K communication links.

There are Q important communication pairs managed by Takahashi in this network. The i-th (1 \leq i \leq Q) communication pair is the communication between base station s_i and base station t_i. Note that the same pair of base stations may appear as multiple communication pairs.

In the network after cutting, define d(s_i, t_i) as the shortest transmission time from base station s_i to base station t_i. If no path exists from base station s_i to base station t_i, then d(s_i, t_i) = +\infty (this also applies if they were unreachable before cutting).

Takahashi wants to keep the transmission time of all communication pairs above a certain level. Therefore, the communication pair with the smallest shortest transmission time among the Q pairs becomes the bottleneck of the entire network. This is called the resilience value of the network after cutting, defined as:

\min_{i=1}^{Q} d(s_i, t_i)

Aoki's goal is to choose which exactly K communication links to cut in order to maximize this resilience value (= create the most disadvantageous situation for Takahashi). That is, the value to find is:

\max_{\text{cutting method}} \min_{i=1}^{Q} d(s_i, t_i)

Here, the maximization is taken over all ways to select exactly K links to cut from the M communication links.

Find this maximum value.

Constraints

  • 2 \leq N \leq 40
  • 1 \leq M \leq 17
  • 0 \leq K \leq M
  • 1 \leq Q \leq 40
  • 1 \leq u_j, v_j \leq N (1 \leq j \leq M)
  • u_j \neq v_j (1 \leq j \leq M) (no self-loops)
  • 1 \leq w_j \leq 10^6 (1 \leq j \leq M)
  • 1 \leq s_i, t_i \leq N (1 \leq i \leq Q)
  • s_i \neq t_i (1 \leq i \leq Q)
  • There is at most one communication link connecting the same pair of base stations (no multi-edges)
  • All input values are integers

Input

N M K Q
u_1 v_1 w_1
u_2 v_2 w_2
\vdots
u_M v_M w_M
s_1 t_1
s_2 t_2
\vdots
s_Q t_Q
  • The first line contains the number of base stations N, the number of communication links M, the number of links to cut K, and the number of important communication pairs Q, separated by spaces.
  • From the 2nd line to the (M + 1)-th line, information about each communication link is given.
  • The (1 + j)-th line (1 \leq j \leq M) gives the base stations u_j, v_j connected by the j-th communication link and its delay time w_j, separated by spaces.
  • From the (M + 2)-th line to the (M + 1 + Q)-th line, information about the important communication pairs is given.
  • The (M + 1 + i)-th line (1 \leq i \leq Q) gives the base stations s_i, t_i of the i-th communication pair, separated by spaces.

Output

Output in one line the maximum resilience value when the choice of communication links to cut is optimal. If the maximum value is +\infty, that is, if there exists a cutting method that makes all Q communication pairs unreachable from s_i to t_i, output INF instead.

Sample Input 1

4 4 1 2
1 2 3
2 3 4
1 3 10
3 4 2
1 3
1 4

Sample Output 1

10

Sample Input 2

3 2 2 1
1 2 5
2 3 7
1 3

Sample Output 2

INF

Sample Input 3

8 10 3 5
1 2 5
2 3 6
3 4 2
4 5 8
5 6 3
6 7 7
7 8 4
1 8 20
2 6 10
3 7 9
1 5
2 8
1 4
5 8
3 6

Sample Output 3

23

Sample Input 4

15 17 5 10
1 2 4
2 3 8
3 4 15
4 5 16
5 6 23
6 7 42
7 8 7
8 9 9
9 10 11
10 11 13
11 12 17
12 13 19
13 14 21
14 15 25
1 5 30
3 10 14
6 15 18
1 15
2 14
4 11
5 9
7 13
1 8
3 12
6 10
2 14
9 15

Sample Output 4

INF

Sample Input 5

40 1 1 40
1 2 1000000
1 2
1 3
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40

Sample Output 5

INF