2024-ho-t2_Construction_Project_2 (JOI JOI)
Time limit: 2 seconds | Memory limit: 1024 MB | Task type: batch
Algorithms: graph theory, dijkstra, shortest path, sorting, binary search

![](_page_0_Picture_0.jpeg)

# Construction Project 2

There are $N$ stations in JOI Kingdom, numbered from 1 to $N$. There are $M$ train lines in JOI Kingdom, numbered from 1 to $M$. The train line $i$ ($1 \le i \le M$) connects station $A_i$ and station $B_i$ bi-directionally, and requires $C_i$ minutes for travel.

You, a minister of JOI Kingdom, decided to construct a new train line as follows.

- You choose integers $u$ and $v$, which satisfy $1 \le u < v \le N$. You construct a new train line, which connects station $u$ and station $v$ bi-directionally, and requires $L$ minutes for travel. Note that you can choose 2 integers such that there already be a train line connecting station $u$ and station $v$.

After you construct a new train line, the King of JOI Kingdom becomes happy if he can move from station $S$ to station $T$ within $K$ minutes by using some train lines. Note that transit times and waiting times for train lines are not considered.

There are $\frac{N(N-1)}{2}$ ways when you choose 2 integers $u$ and $v$, and you want to know how many of these ways make the King happy.

Write a program which, given information of stations, the train lines, and the King's request, calculates the number of ways to choose 2 integers that make the King happy.

## Input

Read the following data from the standard input:

```
N M
S T L K
A1 B1 C1
A2 B2 C2
...
AM BM CM
```

## Output

Write one line to the standard output. The output should contain the number of ways to choose 2 integers that make the King happy.

![](_page_1_Picture_0.jpeg)

## Constraints

- $2 \le N \le 200\,000$.
- $1 \le M \le 200\,000$.
- $1 \le S < T \le N$.
- $1 \le L \le 10^9$.
- $1 \le K \le 10^{15}$.
- $1 \le A_i < B_i \le N$ ($1 \le i \le M$).
- $(A_i, B_i) \ne (A_j, B_j)$ ($1 \le i < j \le M$).
- $1 \le C_i \le 10^9$ ($1 \le i \le M$).
- Given values are all integers.

## Subtasks

1. (8 points) $L = 1$, $K = 2$, $C_i = 1$ ($1 \le i \le M$).
2. (16 points) $N \le 50$, $M \le 50$.
3. (29 points) $N \le 3\,000$, $M \le 3\,000$.
4. (47 points) No additional constraints.

## Sample Input and Sample Output

| Sample Input 1 | Sample Output 1 |
|---|---|
| `7 8`           | `4`             |
| `6 7 1 2`       |                 |
| `1 2 1`         |                 |
| `1 6 1`         |                 |
| `2 3 1`         |                 |
| `2 4 1`         |                 |
| `3 5 1`         |                 |
| `3 7 1`         |                 |
| `4 5 1`         |                 |
| `5 6 1`         |                 |

Suppose you choose $u = 3, v = 6$. You construct a new train line that connects station 3 and station 6 and

![](_page_2_Picture_0.jpeg)

requires 1 minute for travel.

After you construct a new train line, it is possible to move from station 6 to station 7 in 2 minutes by using some train lines as follows. The King becomes happy because he can move from station 6 to station 7 within 2 minutes.

1. Move from station 6 to station 3 by using a train line which connects station 3 and station 6 bi-directionally. This takes 1 minute.
2. Move from station 3 to station 7 by using a train line which connects station 3 and station 7 bi-directionally. This takes 1 minute.

There are 4 ways to choose 2 integers that make the King happy, including this case. Therefore, output 4. This sample input satisfies the constraints of Subtasks 1, 2, 3, 4.

| Sample Input 2 | Sample Output 2 |
|---|---|
| `3 2`           | `3`             |
| `1 3 1 2`       |                 |
| `1 2 1`         |                 |
| `2 3 1`         |                 |

No matter how you choose the 2 integers, the King becomes happy. In other words, there are 3 ways to choose 2 integers that make the King happy. Therefore, output 3.

This sample input satisfies the constraints of Subtasks 1, 2, 3, 4.

| Sample Input 3    | Sample Output 3 |
|---|---|
| `6 4`             | `0`             |
| `2 5 1000000000 1`|                 |
| `1 2 1000000000`  |                 |
| `2 3 1000000000`  |                 |
| `2 4 1000000000`  |                 |
| `5 6 1000000000`  |                 |

No matter how you choose the 2 integers, the King doesn't become happy. Therefore, output 0. This sample input satisfies the constraints of Subtasks 2, 3, 4.

![](_page_3_Picture_0.jpeg)

| Sample Input 4             | Sample Output 4 |
|---|---|
| `18 21`                    | `16`            |
| `4 8 678730772 3000000062` |                 |
| `5 13 805281073`           |                 |
| `8 17 80983648`            |                 |
| `3 8 996533440`            |                 |
| `10 16 514277428`          |                 |
| `2 5 57914340`             |                 |
| `6 11 966149890`           |                 |
| `8 12 532734310`           |                 |
| `2 9 188599710`            |                 |
| `2 3 966306014`            |                 |
| `12 16 656457780`          |                 |
| `16 18 662633078`          |                 |
| `1 15 698078877`           |                 |
| `2 8 665665772`            |                 |
| `2 6 652261981`            |                 |
| `14 15 712798281`          |                 |
| `7 13 571169114`           |                 |
| `13 14 860543313`          |                 |
| `6 7 454251187`            |                 |
| `9 14 293590683`           |                 |
| `6 14 959532841`           |                 |
| `3 11 591245645`           |                 |

This sample input satisfies the constraints of Subtasks 2, 3, 4.

Starter code:

Grader code:

Setup script:

Evaluation script: