[JOI 2024 Final] 建设工程 2 / Construction Project 2

Luogu

IDLGP10206

Time2000ms

Memory1024MB

DifficultyP4

二分2024最短路JOI（日本）双指针 two-pointer

JOI 国有 $N$ 个火车站，编号从 $1$ 到 $N$。另外，JOI 国有 $M$ 条双向铁路线，编号从 $1$ 到 $M$。铁路线 $i\ (1 \leq i \leq M)$ 连接了火车站 $A_{i}$ 和火车站 $B_{i}$，从一个站到另一个站需要花费 $C_i$ 分钟。你是 JOI 国的部长，决定按照以下方式新建一条铁路线：选择两个整数 $u, v\ (1 \leq u<v \leq N)$，在火车站 $u$ 和火车站 $v$ 之间建设一条双向铁路线，从一个站到另一个站需要花费 $L$ 分钟。注意，即使已经有一条连接火车站 $u$ 和火车站 $v$ 的铁路线也可以建设。如果你建设这条铁路线后，可以花费不超过 $K$ 分钟从火车站 $S$ 到火车站 $T$，国王就会高兴。我们不考虑换乘时间和等待时间。你有 $\frac{N(N-1)}{2}$ 种选择两个整数 $u, v$ 的方法，你想知道其中有多少种方法会让国王高兴。给定火车站和铁路线以及国王的要求的信息，编写一个程序，求出其中有多少种选择整数的方法会让国王高兴。 ## Input 第一行包含两个整数 $N,M$。第二行包含四个整数 $S,T,L,K$。接下来 $M$ 行，每行包含三个整数 $A_i, B_i, C_i$，表示第 $i$ 条双向铁路线。 ## Output 输出一行一个整数，表示让国王高兴的两个整数的选择方法有多少种。 [samples] ## Note 对于所有输入数据，满足： - $2 \leq N \leq 2\times 10^5$ - $1 \leq M \leq 2\times 10^5$ - $1 \leq S<T \leq N$ - $1 \leq L \leq 10^{9}$ - $1 \leq K \leq 10^{15}$ - $1 \leq A_{i}<B_{i} \leq N\ (1 \leq i \leq M)$ - $(A_{i}, B_{i}) \neq (A_{j}, B_{j})\ (1 \leq i<j \leq M)$ - $1 \leq C_{i} \leq 10^{9}\ (1 \leq i \leq M)$ 详细子任务附加限制及分值如下表所示。 |子任务| 附加限制| 分值| |:-:|:-:|:-:| |1| $L=1, K=2, C_{i}=1\ (1 \leq i \leq M)$| 8 |2| $N \leq 50, M \leq 50$| 16 |3| $N \leq 3000, M \leq 3000$| 29 |4| 无附加限制| 47

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

6 4
2 5 1000000000 1
1 2 1000000000
2 3 1000000000
2 4 1000000000
5 6 1000000000

Output #3

Input #4

18 21
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

Output #4

API Response (JSON)

{
  "problem": {
    "name": "[JOI 2024 Final] 建设工程 2 / Construction Project 2",
    "description": {
      "content": "JOI 国有 $N$ 个火车站，编号从 $1$ 到 $N$。另外，JOI 国有 $M$ 条双向铁路线，编号从 $1$ 到 $M$。铁路线 $i\\ (1 \\leq i \\leq M)$ 连接了火车站 $A_{i}$ 和火车站 $B_{i}$，从一个站到另一个站需要花费 $C_i$ 分钟。 你是 JOI 国的部长，决定按照以下方式新建一条铁路线： 选择两个整数 $u, v\\ (1 \\leq u<v",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10206"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "JOI 国有 $N$ 个火车站，编号从 $1$ 到 $N$。另外，JOI 国有 $M$ 条双向铁路线，编号从 $1$ 到 $M$。铁路线 $i\\ (1 \\leq i \\leq M)$ 连接了火车站 $A_{i}$ 和火车站 $B_{i}$，从一个站到另一个站需要花费 $C_i$ 分钟。\n\n你是 JOI 国的部长，决定按照以下方式新建一条铁路线：\n\n选择两个整数 $u, v\\ (1 \\leq u<v...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments