{"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$，才能到达市场 $B$。两个市场非常繁华，每天有很多货车往返于两个市场之间。\n\n市长发现，由于限高杆很多，导致货车可能需要绕行才能往返于市场之间，这使得货车在公路系统中的行驶路程变长，增加了对公路系统的损耗，增加了能源的消耗，同时还增加了环境污染。\n\n市长决定要将两段道路中的限高杆拆除，使得市场 $A$ 和市场 $B$ 之间的路程变短。请问最多能减少多长的距离?\n\n## Input\n\n输入的第一行包含两个整数 $n$，$m$，分别表示路口的数量和道路的段数。\n\n接下来 $m$ 行，每行四个整数 $a$，$b$，$c$，$d$，表示路口 $a$ 和路口 $b$ 之间有一段长度为 $c$ 的道路。如果 $d$ 为 $0$，表示这段道路上没有限高杆; 如果 $d$ 为 $1$，表示 这段道路上有限高杆。两个路口之间可能有多段道路。\n\n输入数据保证在不拆除限高杆的情况下，货车能通过公路系统从路口 $1$ 正常行驶到路口 $n$ 。\n\n## Output\n\n输出一行，包含一个整数，表示拆除两段道路的限高杆后，市场 $A$ 和市场 $B$ 之间的路程最大减少多长距离。\n\n[samples]\n\n## Note\n\n**【样例说明】**\n\n只有两段道路有限高杆，全部拆除后，$1$ 到 $n$ 的路程由原来的 $17$ 变为了 $11$，减少了 $6$。\n\n**【评测用例规模与约定】**\n\n对于 $30 \\%$ 的评测样例，$2 \\leq n \\leq 10,1 \\leq m \\leq 20,1 \\leq c \\leq 100$。\n\n对于 $50 \\%$ 的评测样例，$2 \\leq n \\leq 100,1 \\leq m \\leq 1000,1 \\leq c \\leq 1000$。\n\n对于 $70 \\%$ 的评测样例，$2 \\leq n \\leq 1000,1 \\leq m \\leq 10000,1 \\leq c \\leq 10000$。\n\n对于所有评测样例，$2 \\leq n \\leq 10000,2 \\leq m \\leq 10^5,1 \\leq c \\leq 10000$，至少 有两段道路有限高杆。\n\n蓝桥杯 2020 第三轮省赛 AB 组 H 题。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8724","tags":["2020","最短路","蓝桥杯省赛"],"sample_group":[["5 7\n1 2 1 0\n2 3 2 1\n1 3 9 0\n5 3 8 0\n4 3 5 1\n4 3 9 0\n4 5 4 0","6"]],"created_at":"2026-03-03 11:09:25"}}