Description

A Takodachi is a creature which loves cookies.

There is a Takodachi on an undirected graph G = (V, E). There are cookies on the graph, given in a set S. Your job is to tell the Takodachi the distance between it and the closest reachable cookie. If there is no cookie reachable for the Takodachi, it becomes sad. Print "SAD" in capital for it.

Note that:
- G may not be connected.
- G doesn't have multiple edges and self-loops.
- It is possible that there is no cookie within reach of the Takodachi.
- A cookie is reachable if there exist a path between the vertex where the Takodachi is on and the cookie.

Input

The first line of the input contains T — the number of testcases.

The first line of each testcase contains two integers n and m — the size of V and the size of E.

Then m lines follow, each line contains two integers u_i and v_i , being an edge in E.

The next line contains s, the index of the vertex where the Takodachi is.

The next line is |S|, the size of the set S.

Following by the set S itself, denoting which vertices have cookies on, each vertex of the set is seperated by a space.

Output

For each testcase, print the minimum distant to the closest cookie. If the Takodachi cannot reach any cookie, print "SAD" in capital.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a connected graph G = (V, E) and a weight function w: E → N. Let H be a subgraph of G, we define the weight of H w(H) to be the sum of weight of all the edge in H. 

In this problem, you need to answer the weight of the second minimum spanning tree. Namely, let T₁ be a minimum spanning tree of G, find the weight of another spanning tree T₂ such that w(T₁) <= w(T₂) and w(T₂) <= w(T'), where T' is a spanning tree of G, T' ≠ T₁.

Input

There are two integer in the first line, n, m, which represent |V|, |E|.

In the following m lines, each line contains three integer: u, v, c, which is the endpoints of the edge and the weight of the edge respectivlely.

Constraint

• 3 <= n <= 1000
• n <= m <= min{2000, n x (n-1) / 2}
• In each line, 1 <= u, v <= n, u ≠ v
• 1 <= c <= 10⁹
• It is guaranteed that the answer exists.

Output

Output the answer in a single line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

DGL's city has a total of m subway lines, numbered as Line 1, Line 2, ..., Line m. The entire city has n stations, numbered from 1 to n. The cost of taking Line i is a_i, and the cost increases by b_i for each additional station. Line i has c_i stations, and these c_i stations are known. If multiple subway lines pass through the same station, you can transfer to another line at that station, and you can transfer multiple times. Now, DGL wants to take the subway from station s to station t. The waiting time for the subway is negligible. Find the minimum cost, or output -1 if it's not possible to reach the destination.

Note that the subway is bidirectional, so you can travel in either direction along the line. 

Input

The first line contains a number T (1 ≤ T ≤ 5), indicating the number of testcases.

For each test case:

• The first line contains four positive integers n, m, s, t, representing the number of stations, the number of subway lines, the starting station, and the destination station.
• From the second line to the m+1-th line, each line contains three numbers a_i, b_i, c_i, representing the cost of taking Line i, the additional cost per station for Line i, and the number of stations on Line i. The next c_i numbers represent the station numbers on Line i.

Output

Output a single number representing the minimum cost. If it's not possible to reach the destination, output -1.

Remarks

• 1 ≤ n ≤ 1000
• 1 ≤ m ≤ 500
• 1 ≤ s, t ≤ n
• 1 ≤ a_i, b_i ≤ 100
• 1 ≤ c_i ≤ n
• ∑ c_i ≤ 10⁵

Sample Explanation

For the first testcase, Taking Line 1 costs 2 units. Moving from Station 1 to Station 3 costs 2 units. Transferring to Line 2 costs 2 units. Moving from Station 3 to Station 4 costs 1 unit. Therefore, the minimum total cost is 7 units.

For the second testcase, there is no line can go to Station 3.

Subtasks

• For testcases 1 ~ 2: m = 1
• For testcases 3 ~ 4: n, m ≤ 100
• For testcases 5~10: no other restriction.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You are given an undirected graph with N vertices and M edges.

It is guaranteed that the graph is simple (no self-loops or multiple edges).

The graph may be unconnected.

Your task is to find how many ways you can add exactly one edges such that the graph becomes connected (meaning that there exists a path between every pair of vertices).Please note that the result graph must be simple, that is you cannot add self-loop or multiple edge to the graph.

Input

The first line of input contains three integers: N, M.

The following M lines of input contain two integers each: u ᵢ and v ᵢ for line i.

Constraints

• 1 <= N <= 80000
• 1 <= M <= min( N(N-1)/2, 1000000)
• 1 <= u ᵢ , v ᵢ <= N

Subtask

• For 60% of the test cases, N is less than or equal to 20.

• For 40% of the test cases, there are no additional constraints.

Output

Output a single integer representing the number of ways to add exactly one edges such that the graph becomes connected.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

2024 DS Exam 4

• 考試當天座位表會貼在教室前面，按座位表入座
• 考試當天請攜帶學生證以利核對身份
• 當天會提供計算紙，除文具及學生證之外其他物品請勿攜帶至座位
• 考試當天會斷網，但我們會提供上課的講義給同學參考
• 嚴禁作弊，違者當次考試直接零分並依照校規處理
• 考試當天需要簽到，簽到後表示同意以上規定
• Lab 的講義已經放在 14390.cpp 裡面，請同學把檔案下載下來後把附檔名改為.zip並解壓縮即可查看內容。

2024 Data Structures, Exam 4

Instructions:

• The seating chart will be posted at the front of the classroom on the day of the exam. Please take your seat according to the chart.
• On the day of the exam, please bring your student ID for identity verification.
• Calculation paper will be provided on the day of the exam. Apart from stationery and your student ID, do not bring any other items to your seat.
• The internet will be disconnected on the day of the exam, but we will provide lecture notes for reference.
• Cheating is strictly prohibited. Anyone caught cheating will receive a zero for the exam and will be dealt with according to school regulations.
• You will need to sign in on the day of the exam. Signing in indicates your agreement to the above rules.
• Lecture notes for Labs have been placed in the file named 14390.cpp. Please download the file, change the extension to .zip, and unzip it to view the contents.

Input

Output

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss