A - Graph

Time Limit: 3 sec / Memory Limit: 256 MB

配点 : 700 点

問題文

高橋君は N 頂点 M 辺からなる連結な無向グラフを見つけました。頂点には 1,2,...,N の番号がついており、辺 i は頂点 a_i と頂点 b_i をつないでいます。また、辺には重さがあり、辺 i の重さは c_i です。

そこで、高橋君は Q 回ゲームをし、 i 回目のゲームで頂点 S_i と頂点 T_i を使うことにしました。i 回目のゲームでは辺の部分集合を選び、どの頂点にも頂点 S_i または頂点 T_i から選ばれた辺のみをたどってたどり着けるようにしたいです。

各ゲームにおいて、高橋君が選ぶ辺の重みの総和として考えられる最小値を求めてください。

制約

  • 1 ≦ N ≦ 4,000
  • 1 ≦ M ≦ 400,000
  • 1 ≦ Q ≦ 100,000
  • 1 ≦ a_i,b_i,S_i,T_i ≦ N
  • 1 ≦ c_i ≦ 10^{9}
  • a_i \neq b_i
  • S_i \neq T_i
  • 入力で与えられるグラフは連結である。

部分点

  • 200 点分のデータセットでは、Q = 1 が成立する。
  • 別の 300 点分のデータセットでは、Q ≦ 3000 が成立する。

入力

入力は以下の形式で標準入力から与えられる。

N M 
a_1 b_1 c_1
a_2 b_2 c_2
:
a_M b_M c_M
Q
S_1 T_1
S_2 T_2
:
S_Q T_Q

出力

Q 行出力し、i 行目には i 回目のゲームにおいて高橋君が選ぶ辺の重みの総和として考えられる最小値を出力せよ。

入力例1

4 3
1 2 3
2 3 4
3 4 5
2
2 3
1 4

出力例1

8
7

各ゲームについて見ると、

  • 1 回目のゲームでは辺 1 と辺 3 を選ぶことで、最小値 8 が達成されます。
  • 2 回目のゲームでは辺 1 と辺 2 を選ぶことで、最小値 7 が達成されます。

入力例2

4 6
1 3 5
4 1 10
2 4 6
3 2 2
3 4 5
2 1 3
1
2 3

出力例2

8

この入力はどちらの部分点の制約も満たします。

Score : 700 points

Problem Statement

Takahashi found an undirected connected graph with N vertices and M edges. The vertices are numbered 1 through N. The i-th edge connects vertices a_i and b_i, and has a weight of c_i.

He will play Q rounds of a game using this graph. In the i-th round, two vertices S_i and T_i are specified, and he will choose a subset of the edges such that any vertex can be reached from at least one of the vertices S_i or T_i by traversing chosen edges.

For each round, find the minimum possible total weight of the edges chosen by Takahashi.

Constraints

  • 1 ≦ N ≦ 4,000
  • 1 ≦ M ≦ 400,000
  • 1 ≦ Q ≦ 100,000
  • 1 ≦ a_i,b_i,S_i,T_i ≦ N
  • 1 ≦ c_i ≦ 10^{9}
  • a_i \neq b_i
  • S_i \neq T_i
  • The given graph is connected.

Partial Scores

  • In the test set worth 200 points, Q = 1.
  • In the test set worth another 300 points, Q ≦ 3000.

Input

The input is given from Standard Input in the following format:

N M
a_1 b_1 c_1
a_2 b_2 c_2
:
a_M b_M c_M
Q
S_1 T_1
S_2 T_2
:
S_Q T_Q

Output

Print Q lines. The i-th line should contain the minimum possible total weight of the edges chosen by Takahashi.

Sample Input 1

4 3
1 2 3
2 3 4
3 4 5
2
2 3
1 4

Sample Output 1

8
7

We will examine each round:

  • In the 1-st round, choosing edges 1 and 3 achieves the minimum total weight of 8.
  • In the 2-nd round, choosing edges 1 and 2 achieves the minimum total weight of 7.

Sample Input 2

4 6
1 3 5
4 1 10
2 4 6
3 2 2
3 4 5
2 1 3
1
2 3

Sample Output 2

8

This input satisfies the additional constraints for both partial scores.
B - Problem where Commas Separate Digits

Time Limit: 3 sec / Memory Limit: 256 MB

配点 : 1000 点

問題文

1 から 9 までの数字のみで構成された文字列 S が与えられます。 この文字列に、K 個以下のカンマ(,)を 挿入し、複数の数に分けたいと思います。

この操作をした際に現れる数の最大値を最小化したとき、その値を出力してください。

制約

  • 0 ≦ K < |S| ≦ 100,000
  • S は 1 から 9 までの数字のみからなる。

部分点

  • 100 点分のデータセットでは、|S| ≦ 2 が成り立つ。
  • 別の 100 点分のデータセットでは、|S| ≦ 16 が成り立つ。
  • 別の 200 点分のデータセットでは、|S| ≦ 100 が成り立つ。
  • 別の 200 点分のデータセットでは、|S| ≦ 2,000 が成り立つ。

入力

入力は以下の形式で標準入力から与えられる。

K
S

出力

求める整数を 1 行で出力しなさい。

入力例 1

2
15267315

出力例 1

315

152, 67, 315 と区切ると、最大値が 315 となり、これが答えとなります。

入力例 2

0
12456174517653111

出力例 2

12456174517653111

12456174517653111 がそのまま答えとなります。

入力例 3

8
127356176351764127645176543176531763517635176531278461856198765816581726586715987216581

出力例 3

5317635176

Score : 1000 points

Problem Statement

You are given a string S consisting of digits between 1 and 9, inclusive. You will insert at most K commas (,) into this string to separate it into multiple numbers.

Your task is to minimize the maximum number among those produced by inserting commas. Find minimum possible such value.

Constraints

  • 0 ≦ K < |S| ≦ 100,000
  • S consists of digits between 1 and 9, inclusive.

Partial Scores

  • In the test set worth 100 points, |S| ≦ 2.
  • In the test set worth another 100 points, |S| ≦ 16.
  • In the test set worth another 200 points, |S| ≦ 100.
  • In the test set worth another 200 points, |S| ≦ 2,000.

Input

The input is given from Standard Input in the following format:

K
S

Output

Print the minimum possible value.

Sample Input 1

2
15267315

Sample Output 1

315

When the string is separated into 152, 67 and 315, the maximum among these is 315, which is the minimum possible value.

Sample Input 2

0
12456174517653111

Sample Output 2

12456174517653111

12456174517653111 itself is the answer.

Sample Input 3

8
127356176351764127645176543176531763517635176531278461856198765816581726586715987216581

Sample Output 3

5317635176