## NOI '18 Problem 1 - Return

View as PDF

Points: 17 (partial)
Time limit: 4.0s
Memory limit: 512M

Problem type

You are given an undirected connected graph with vertices labeled from to , and edges, where the -th edge has length and altitude .

You are given queries. In each query, you are given a starting vertex , a water level . A water level indicates that there is water on the edges that have . You can drive a car starting from only through the edges that have no water, and then get out of the car at any vertex and walk to vertex . You want to find the minimum sum of lengths of edges that you need to walk through in a path.

In some tests, the queries are forced online. See more details in the Input Specification/Constraints.

#### Input Specification

The first line contains an integer , the number of test cases.

For each test case,

• The first line contains two non-negative numbers , the number of vertices, and , the number of edges.
• Each of the next lines contains four integers , indicating that the -th edge is between vertices and , and has length and altitude .
• The next line contains three integers, . is a constant used in calculating the input each time, is the highest possible in all queries.
• Each of the next lines contains two integers and . Let denote the answer in the last query ( if this is the first query). Then in this query, you are starting from vertex and water level . It is guaranteed that , .

#### Output Specification

For each query, output the answer on its own line.

#### Constraints

For all test files, . For all test cases in a file:

• .
• For all edges, , , .
• The graph is connected.

The following terminology is used in the constraint table:

• Graph Property:
• Bamboo: , and for each edge we have .
• Tree:
• Altitude:
• One kind: For all edges, .
• Forced Online:
• Yes:
• No:

"no guarantee" means that there is no guarantee on the property of test data.

No. Graph Property Altitute Forced Online
no guarantee one kind No
Bamboo no guarantee
Tree
Yes
no guarantee No
Yes

#### Sample Input 1

1
4 3
1 2 50 1
2 3 100 2
3 4 50 1
5 0 2
3 0
2 1
4 1
3 1
3 2

#### Sample Output 1

0
50
200
50
150

#### Explanation for Sample Output 1

Day has no rain. so you can just travel directly.

Days , , have the same situation: the edges between and have water.

On day , starting from , you can only go to , which doesn't help returning, so you have to walk.

On day , the only edge out of has water, so you again have to walk.

On day , you can first take the car to , and then walk home.

On day , all edges have water, so you have to walk.

#### Sample Input 2

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

#### Sample Output 2

0
2
3
1

#### Explanation for Sample Output 2

This test case is forced online.

On day the answer is , so day has , .

On day , the answer is , so day has , .

On day , the answer is , so day has , .