13281328 SUSTech Online Judge
Problem 1328 --Metro

## 1328: Metro

Time Limit: 2 Sec  Memory Limit: 512 MB
Submit: 18  Solved: 6
[Submit][Status][Web Board]

## Description

Yuki is a thrifty girl and she always tries her best to economize on money.

Yuki lives in Guangzhou, a metropolis in southern China. Everyday she needs to take the metro for her study. The metro system map of Guangzhou can be considered as a graph $$G$$, where there are totally $$n$$ nodes as stations and $$m$$ bidirectional edges with given distances linking these stations.

Yuki's home is located nearby station $$S$$ and her school is located nearby station $$T$$. Also, she needs to go to school $$k$$ times every month, that means totally taking metro $$2k$$ times ($$k$$ times from $$S$$ to $$T$$ and $$k$$ times from $$T$$ to $$S$$, the first journey must be started at $$S$$).

The rules of fares in Guangzhou metro are shown as following:

• A journey shorter than 4 km (inclusive), costs ¥2.
• ¥1 is charged for every 4 km after 4 km, every 6 km after 12 km, and every 8 km after 24 km.
• If the departure and arrival station of the journey is the same, also costs ¥2.

Also Yangcheng Tong offers discounts for rides on the metro. Within each month, a 5% discount is available for the first 15 journeys and a 40% discount for all journeys beyond.

Now Yuki taps Yangcheng Tong to take the metro and she wants to know the minimum fares for her to pay every month.

## Input

The first line contains four integers: $$n$$, $$m$$, $$k$$ and $$q$$ $$(1\leq n\leq 100, 1\leq m\leq 1\ 000, 1\leq k\leq 30, 1\leq q\leq 10)$$--- the number of stations, edges, times needed to go to school and the total number of queries respectively.

Each of the following $$m$$ lines contains three integer $$u_i$$, $$v_i$$ and $$w_i$$ $$(1\leq u_i,v_i\leq n, 1\leq w_i\leq 20\ 000,u_i\neq v_i)$$, meaning that there is a bidirectional edge from $$u_i$$ to $$v_i$$ with distance $$w_i$$. Please be reminded that $$w_i$$ is in the unit of meter.

Each of the following $$q$$ lines contains two integer $$S_i, T_i$$ $$(S_i\neq T_i)$$ --- a query where $$S=S_i$$ and $$T=T_i$$. It is guaranteed that $$S_i$$ and $$T_i$$ are connected.

## Output

For each of the queries, print one line with the result --- the minimum cost Yuki needs to pay every month. The result should be accurate to two decimal places.

## Sample Input

7 7 30 1
1 2 4000
2 3 4000
3 4 3000
4 5 6000
5 6 2000
1 7 5000
7 6 9000
1 6

## Sample Output

201.25

## HINT

A tweet may be helpful for you to solve the problem.
You need to think carefully about the departure and arrival of the first 15 journeys. [Submit][Status]