[蓝桥杯 2020 省 AB3] 限高杆

Luogu
IDLGP8724
Time1000ms
Memory128MB
DifficultyP4
2020最短路蓝桥杯省赛
某市有 $n$ 个路口,有 $m$ 段道路连接这些路口,组成了该市的公路系统。其中一段道路两端一定连接两个不同的路口。道路中间不会穿过路口。 由于各种原因,在一部分道路的中间设置了一些限高杆,有限高杆的路段货车无法通过。 在该市有两个重要的市场 $A$ 和 $B$,分别在路口 $1$ 和 $n$ 附近,货车从市场 $A$ 出发,首先走到路口 $1$,然后经过公路系统走到路口 $n$,才能到达市场 $B$。两个市场非常繁华,每天有很多货车往返于两个市场之间。 市长发现,由于限高杆很多,导致货车可能需要绕行才能往返于市场之间,这使得货车在公路系统中的行驶路程变长,增加了对公路系统的损耗,增加了能源的消耗,同时还增加了环境污染。 市长决定要将两段道路中的限高杆拆除,使得市场 $A$ 和市场 $B$ 之间的路程变短。请问最多能减少多长的距离? ## Input 输入的第一行包含两个整数 $n$,$m$,分别表示路口的数量和道路的段数。 接下来 $m$ 行,每行四个整数 $a$,$b$,$c$,$d$,表示路口 $a$ 和路口 $b$ 之间有一段长度为 $c$ 的道路。如果 $d$ 为 $0$,表示这段道路上没有限高杆; 如果 $d$ 为 $1$,表示 这段道路上有限高杆。两个路口之间可能有多段道路。 输入数据保证在不拆除限高杆的情况下,货车能通过公路系统从路口 $1$ 正常行驶到路口 $n$ 。 ## Output 输出一行,包含一个整数,表示拆除两段道路的限高杆后,市场 $A$ 和市场 $B$ 之间的路程最大减少多长距离。 [samples] ## Note **【样例说明】** 只有两段道路有限高杆,全部拆除后,$1$ 到 $n$ 的路程由原来的 $17$ 变为了 $11$,减少了 $6$。 **【评测用例规模与约定】** 对于 $30 \%$ 的评测样例,$2 \leq n \leq 10,1 \leq m \leq 20,1 \leq c \leq 100$。 对于 $50 \%$ 的评测样例,$2 \leq n \leq 100,1 \leq m \leq 1000,1 \leq c \leq 1000$。 对于 $70 \%$ 的评测样例,$2 \leq n \leq 1000,1 \leq m \leq 10000,1 \leq c \leq 10000$。 对于所有评测样例,$2 \leq n \leq 10000,2 \leq m \leq 10^5,1 \leq c \leq 10000$,至少 有两段道路有限高杆。 蓝桥杯 2020 第三轮省赛 AB 组 H 题。
Samples
Input #1
5 7
1 2 1 0
2 3 2 1
1 3 9 0
5 3 8 0
4 3 5 1
4 3 9 0
4 5 4 0
Output #1
6
API Response (JSON)
{
  "problem": {
    "name": "[蓝桥杯 2020 省 AB3] 限高杆",
    "description": {
      "content": "某市有 $n$ 个路口,有 $m$ 段道路连接这些路口,组成了该市的公路系统。其中一段道路两端一定连接两个不同的路口。道路中间不会穿过路口。 由于各种原因,在一部分道路的中间设置了一些限高杆,有限高杆的路段货车无法通过。 在该市有两个重要的市场 $A$ 和 $B$,分别在路口 $1$ 和 $n$ 附近,货车从市场 $A$ 出发,首先走到路口 $1$,然后经过公路系统走到路口 $n$,才能到达市",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8724"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "某市有 $n$ 个路口,有 $m$ 段道路连接这些路口,组成了该市的公路系统。其中一段道路两端一定连接两个不同的路口。道路中间不会穿过路口。\n\n由于各种原因,在一部分道路的中间设置了一些限高杆,有限高杆的路段货车无法通过。\n\n在该市有两个重要的市场 $A$ 和 $B$,分别在路口 $1$ 和 $n$ 附近,货车从市场 $A$ 出发,首先走到路口 $1$,然后经过公路系统走到路口 $n$,才能到达市...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments